0/1 إصلاح مشكلة حقيبة الظهر باستخدام مثال البرمجة الديناميكية

ما هي مشكلة الحقيبة؟

مشكلة الحقيبة الخوارزمية هي مشكلة مفيدة جدًا في التوافقيات. يوجد في السوبر ماركت n عبوات (n ≥ 100) الحزمة i لها وزن W[i] ≥ 100 وقيمة V[i] ≥ 100. يقتحم لص السوبر ماركت، ولا يستطيع اللص حمل وزن يتجاوز M (M ≥ 100) ). المشكلة التي يجب حلها هنا هي: ما هي الطرود التي سيأخذها اللص للحصول على أعلى قيمة؟

الإدخال:

• الحد الأقصى للوزن M وعدد الطرود n.
• صفيف الوزن W[i] والقيمة المقابلة V[i].

الإخراج:

• تعظيم القيمة والوزن المقابل في السعة.
• ما هي الحزم التي سيأخذها اللص؟

يمكن تقسيم خوارزمية حقيبة الظهر إلى نوعين:

• مشكلة حقيبة 0/1 باستخدام البرمجة الديناميكية. في هذا النوع من خوارزمية حقيبة الظهر، يمكن أخذ كل حزمة أو عدم أخذها. علاوة على ذلك، لا يجوز للسارق أن يأخذ جزءًا صغيرًا من الطرد المأخوذ أو يأخذ طردًا أكثر من مرة. يمكن حل هذا النوع من خلال نهج البرمجة الديناميكية.
• خوارزمية مشكلة الحقيبة الكسرية. يمكن حل هذا النوع عن طريق استراتيجية الجشع.

كيفية حل مشكلة الحقيبة باستخدام البرمجة الديناميكية مع المثال

في استراتيجية فرق تسد، تقوم بتقسيم المشكلة المراد حلها إلى مشاكل فرعية. وتنقسم المشاكل الفرعية إلى مشاكل فرعية أصغر. ستستمر هذه المهمة حتى تحصل على مشاكل فرعية يمكن حلها بسهولة. ومع ذلك، في عملية هذا التقسيم، قد تواجه نفس المشكلة عدة مرات.

الفكرة الأساسية للبرمجة الديناميكية باستخدام حقيبة الظهر هي استخدام جدول لتخزين حلول المشاكل الفرعية المحلولة. إذا واجهت مشكلة فرعية مرة أخرى، فما عليك سوى إدخال الحل في الجدول دون الحاجة إلى حلها مرة أخرى. لذلك، فإن الخوارزميات المصممة بواسطة البرمجة الديناميكية فعالة للغاية.

لحل مشكلة باستخدام البرمجة الديناميكية، يجب عليك القيام بالمهام التالية:

• إيجاد حلول لأصغر المشاكل الفرعية.
• اكتشف الصيغة (أو القاعدة) لبناء حل للمشكلة الفرعية من خلال حلول حتى لأصغر المشكلات الفرعية.
• إنشاء جدول يخزن فيه حلول المسائل الفرعية. ثم احسب حل المشكلة الفرعية وفقًا للصيغة الموجودة واحفظها في الجدول.
• من المسائل الفرعية التي تم حلها تجد حل المشكلة الأصلية.

تحليل مشكلة حقيبة الظهر 0/1

عند تحليل مشكلة حقيبة الظهر 0/1 باستخدام البرمجة الديناميكية، يمكنك العثور على بعض النقاط الملحوظة. تعتمد قيمة خوارزمية الحقيبة على عاملين:

1. كم عدد الحزم التي يتم النظر فيها
2. الوزن المتبقي الذي يمكن للحقيبة تخزينه.

لذلك، لديك كميتين متغيرتين.

مع البرمجة الديناميكية، لديك معلومات مفيدة:

1. ستعتمد الدالة الهدف على كميتين متغيرتين
2. سيكون جدول الخيارات عبارة عن جدول ثنائي الأبعاد.

إذا كان استدعاء B[i] [j] هو أقصى قيمة ممكنة عن طريق الاختيار في الحزم {1، 2، ...، i} مع حد الوزن j.

• القيمة القصوى عند تحديدها في عدد n من الحزم مع حد الوزن M هي B[n][M]. بمعنى آخر: عندما تكون هناك حزم i للاختيار منها، يكون B[i][j] هو الوزن الأمثل عندما يكون الحد الأقصى لوزن الحقيبة هو j.
• الوزن الأمثل دائمًا أقل من أو يساوي الحد الأقصى للوزن: B[i][j] ≥ j.

على سبيل المثال: B[4][10] = 8. هذا يعني أنه في الحالة المثالية، يكون الوزن الإجمالي للطرود المحددة هو 8، عندما يكون هناك 4 طرود أولى للاختيار من بينها (الحزمة الأولى إلى الرابعة) والحد الأقصى للوزن عدد العناصر الموجودة في الحقيبة هو 1. وليس من الضروري أن يتم تحديد جميع العناصر الأربعة.

صيغة لحساب B[i][j]

الإدخال، يمكنك تحديد:

• W[i]، V[i] هما بدورهما وزن وقيمة الحزمة i، التي فيها i {1، …، ن}.
• M هو الحد الأقصى للوزن الذي يمكن أن تحمله الحقيبة.

في حالة وجود حزمة واحدة فقط للاختيار منها. تقوم بحساب B[1] [j] لكل j: وهو ما يعني الحد الأقصى لوزن الحقيبة ≥ وزن الحزمة الأولى

B[1][j] = W[1]

مع حد الوزن j، الاختيارات المثالية بين الحزم {1، 2، …، i – 1، i} للحصول على أكبر قيمة سيكون لها احتمالين:

• إذا لم يتم تحديد الحزمة i، فإن B[i] [j] هي أقصى قيمة ممكنة عن طريق الاختيار من بين الحزم {1، 2، ...، i - 1} مع حد وزن j. لديك:

B[i][j] = B[i – 1][j]

• إذا تم تحديد الحزمة i (بالطبع خذ هذه الحالة فقط عند W[i] ≥ j) فإن B[i][j] تساوي القيمة V[i] للحزمة i بالإضافة إلى أنه يمكن الحصول على القيمة القصوى عن طريق الاختيار من بين الطرود {1، 2، …، i – 1} مع حد الوزن (j – W[i]). أي من حيث القيمة التي لديك:

B[i][j] = V[i] + B[i – 1][j – W[i]]

نظرًا لإنشاء B[i] [j]، وهو الحد الأقصى للقيمة الممكنة، فإن B [i] [j] سيكون الحد الأقصى للقيمتين المذكورتين أعلاه.

أساس البرمجة الديناميكية

لذا، عليك أن تفكر فيما إذا كان من الأفضل اختيار الحزمة i أم لا. من هناك لديك الصيغة العودية كما يلي:

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]

من السهل رؤية B[0][j] = أقصى قيمة ممكنة عن طريق الاختيار من 0 package = 0.

احسب جدول الخيارات

يمكنك إنشاء جدول خيارات بناءً على الصيغة العودية المذكورة أعلاه. للتحقق مما إذا كانت النتائج صحيحة (إن لم تكن صحيحة، قم بإعادة بناء الدالة الهدف B[i][j]). من خلال إنشاء وظيفة الهدف B[i][j] وجدول الخيارات، ستقوم بتوجيه عملية التتبع.

يتضمن جدول الخيارات B خطوط n + 1، وأعمدة M + 1،

• أولاً، مليئة بأساسيات البرمجة الديناميكية: السطر 0 يشمل جميع الأصفار.
• باستخدام الصيغ العودية، استخدم السطر 0 لحساب السطر 1، واستخدم السطر 1 لحساب السطر 2، وما إلى ذلك ... حتى يتم حساب جميع الأسطر.

أثر

عند حساب جدول الخيارات، أنت مهتم بـ B[n][M] وهي القيمة القصوى التي يتم الحصول عليها عند الاختيار في جميع الحزم n مع حد الوزن M.

• If ب[ن] [م] = ب [ن - 1] [م] ثم لم يتم تحديد الحزمة n، يمكنك تتبع B[n – 1][M].
• If ب[ن] [م] ≠ ب [ن - 1] [م]، لاحظت أن التحديد الأمثل يحتوي على الحزمة n والتتبع B[n – 1][M – W[n]].

استمر في التتبع حتى تصل إلى الصف 0 من جدول الخيارات.

خوارزمية للبحث في جدول الخيارات للعثور على الحزم المحددة

ملاحظة: إذا كان B[i] [j] = B [i - 1] [j]، فلن يتم تحديد الحزمة i. B[n][W] هي القيمة الإجمالية المثالية للحزمة الموضوعة في الحقيبة.

خطوات التتبع:

• الخطوة الأولى:: ابتداء من i = n، j = M.
• الخطوة الأولى:: انظر في العمود j، من الأسفل، تجد السطر i بحيث يكون B[i][j] > B[i – 1][j]. قم بوضع علامة على الحزمة المحددة i: Select [i] = true;
• الخطوة الأولى:: j = B[i][j] – W[i]. إذا كانت j > 0، انتقل إلى الخطوة 2، وإلا انتقل إلى الخطوة 4
• الخطوة الأولى:: بناءً على جدول الخيارات لطباعة الحزم المحددة.

Java رمز

public void knapsackDyProg(int W[], int V[], int M, int n) {
	int B[][] = new int[n + 1][M + 1];
	
	for (int i=0; i<=n; i++)
		for (int j=0; j<=M; j++) {
			B[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= M; j++) {
			B[i][j] = B[i - 1][j];
			
			if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
				B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; 
			}
			
			System.out.print(B[i][j] + " ");
		}
		System.out.print("\n");
	}
	
	System.out.println("Max Value:\t" + B[n][M]);
	
	System.out.println("Selected Packs: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}

شرح كود حقيبة الظهر:

1. إنشاء جدول ب[][]. قم بتعيين القيمة الافتراضية لكل خلية هي 0.
2. أنشئ الجدول B[][] بطريقة تصاعدية. احسب جدول الخيارات باستخدام صيغة الاسترجاع.
3. احسب B[i][j]. إذا لم تقم بتحديد الحزمة i.
4. ثم قم بالتقييم: إذا حددت الحزمة i، فسيكون ذلك أكثر فائدة ثم قم بإعادة تعيين B[i][j].
5. تتبع الجدول من الصف n إلى الصف 0.
6. إذا اخترت الحزمة ن. بمجرد تحديد الحزمة n، يمكنك فقط إضافة الوزن M – W[n – 1].

في هذا البرنامج التعليمي، لديك مثالين. إليك كود جافا لتشغيل البرنامج أعلاه مع مثالين:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

لديك الإخراج:

• المثال الأول:

0 0 0 3 3 3 3 3 3 3 3 3 
0 0 0 3 4 4 4 7 7 7 7 7 
0 0 0 3 4 4 4 7 7 8 8 8 
0 0 0 3 4 4 4 7 7 10 10 10 
0 0 0 3 4 4 4 7 8 10 10 11 
Max Value:	11
Selected Packs: 
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

• المثال الثاني:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs: 
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2