Algorithms/0 1 knapsack

المطلوب في مسألة حقيبة الظهر ‎0-1 هو وضع مجموعة من العناصر ذات أوزان وقيم محددة في حقيبة ظهر تتسع لعدد معين من العناصر مع مراعاة الحصول على أكبر قيمة ممكنة لمجموع قيم العناصر الموجودة في الحقيبة، ولكن بشرط عدم وضع جزء من العنصر فإما أن يوضع العنصر كاملًا أو لا يوضع إطلاقًا.

وبمعنى آخر، هناك مصفوفتان من الأعداد الصحيحة val[0..n-1]‎ و wt[0..n-1]‎ واللتان تمثّلان قيم وأوزان العناصر المراد وضعها في الحقيبة ذات الوزن W. والمطلوب هو إيجاد أكبر مجموعة فرعية من المصفوفة val[]‎ بشرط أن يكون مجموع أوزان العناصر في هذه المجموعة الفرعية أصغر من سعة الحقيبة أو مساويًا لها، مع ملاحظة أنّه لا يسمح بتقسيم العناصر فإمّا أن يوضع العنصر كاملًا أو أنّه لن يدخل الحقيبة.

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

البنية الفرعية المثالية

يمكن ملاحظة حالتين لكل عنصر عند النظر إلى كل المجموعات الفرعية من العناصر:

1. العنصر موجود في المجموعة الفرعية المثالية.
2. العنصر غير موجود في المجموعة الفرعية المثالية.

هذا يعني أنّ القيمة العظمى التي يمكن الحصول عليها من n عنصر هي القيمة العظمى من بين القيمتين التاليتين:

1. القيمة العظمى التي يمكن الحصول عليها من n-1 عنصر ومن وسعة الحقيبة W (من دون العنصر ذي الترتيب n).
2. قيمة العنصر ذي الترتيب n إضافة إلى القيمة العظمى التي يمكن الحصول عليها من n-1 عنصر وسعة الحقيبة W مطروحًا منه وزن العنصر ذي الترتيب n (مع العنصر ذي الترتيب n).

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

مسائل فرعية متداخلة

تعرض الشيفرات التالية الحلّ التعاودي لمسألة حقيبة الظهر ‎0-1 في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// دالة مساعدة تعيد القيمة الأكبر بين القيمتين المعطاتين
int max(int a, int b) { return (a > b)? a : b; } 

// W تعيد الدالة أكبر قيمة يمكن وضعها في حقيبة الظهر ذات السعة
int knapSack(int W, int wt[], int val[], int n) 
{ 
	
// الحالة الأساس
if (n == 0 || W == 0) 
	return 0; 

// إن كان وزن العنصر ذي الترتيب المعطى
// أكبر من سعة حقيبة الظهر فليس بالإمكان
// إضافة هذا العنصر إلى الحل المثالي
if (wt[n-1] > W) 
	return knapSack(W, wt, val, n-1); 

// تعيد الدالة أكبر قيمة من بين الحالتين:
// (1) تضمين العنصر ذي الترتيب المعطى
// (2) عدم تضمين العنصر
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), 
					knapSack(W, wt, val, n-1) ); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int val[] = {60, 100, 120}; 
	int wt[] = {10, 20, 30}; 
	int W = 50; 
	int n = sizeof(val)/sizeof(val[0]); 
	cout<<knapSack(W, wt, val, n); 
	return 0; 
}

• بايثون:

# دالة مساعدة تعيد القيمة الأكبر بين القيمتين المعطاتين
def knapSack(W , wt , val , n): 

	# الحالة الأساس 
	if n == 0 or W == 0 : 
		return 0

	# إن كان وزن العنصر ذي الترتيب المعطى 
	# أكبر من سعة حقيبة الظهر فليس بالإمكان
	# إضافة هذا العنصر إلى الحل المثالي
	if (wt[n-1] > W): 
		return knapSack(W , wt , val , n-1) 

	# تعيد الدالة أكبر قيمة من بين الحالتين: 
	# (1) تضمين العنصر ذي الترتيب المعطى
	# (2) عدم تضمين العنصر
	else: 
		return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
				knapSack(W , wt , val , n-1)) 


# اختبار الدوال السابقة
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
print knapSack(W , wt , val , n)

• جافا:

/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack 
{ 

	// دالة مساعدة تعيد القيمة الأكبر بين القيمتين المعطاتين 
	static int max(int a, int b) { return (a > b)? a : b; } 
	
	// W تعيد الدالة أكبر قيمة يمكن وضعها في حقيبة الظهر ذات السعة
	static int knapSack(int W, int wt[], int val[], int n) 
	{ 
		// الحالة الأساس 
	if (n == 0 || W == 0) 
		return 0; 
	
	// إن كان وزن العنصر ذي الترتيب المعطى
	// أكبر من سعة حقيبة الظهر فليس بالإمكان
	// إضافة هذا العنصر إلى الحل المثالي
	if (wt[n-1] > W) 
	return knapSack(W, wt, val, n-1); 
	
	// تعيد الدالة أكبر قيمة من بين الحالتين: 
	// (1) تضمين العنصر ذي الترتيب المعطى
	// (2) عدم تضمين العنصر
	else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), 
					knapSack(W, wt, val, n-1) 
					); 
	} 

	
// اختبار الدوال السابقة 
public static void main(String args[]) 
{ 
		int val[] = new int[]{60, 100, 120}; 
		int wt[] = new int[]{10, 20, 30}; 
	int W = 50; 
	int n = val.length; 
	System.out.println(knapSack(W, wt, val, n)); 
	} 
}

يلاحظ أن الدوال السابقة تعالج المسائل الفرعية ذاتها مرارًا وتكرارًا.

يعرض الشكل التالي شجرة التعاود للقيم:

wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}

                       K(3, 2)         ---------> K(n, W)
                   /            \ 
                 /                \               
            K(2,2)                  K(2,1)
          /       \                  /    \ 
        /           \              /        \
       K(1,2)      K(1,1)        K(1,1)     K(1,0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)

يلاحظ أنّ الدالة K(1,1)‎ تستدعى مرتين، ونتيجة لذلك يبلغ التعقيد الزمني للطريقة التعاودية في حل المسألة المقدار O(n^2)‎.

لمّا كانت المسائل الفرعية تعالج بصورة متكررة، فهذا يعني أنّ هذه المسألة تمتتع بخاصية المسائل الفرعية المتداخلة.

ولمّا كانت هذه المسألة تتمتع بالخاصيتين الرئيسيتين لمسائل البرمجة الديناميكية، فيمكن حلّ هذه المسألة باستخدام أسلوب البرمجة الديناميكية، ويمكن تجنّب تكرار حساب المسائل الفرعية بإنشاء مصفوفة مؤقتة (لتكن K[][]‎) بطريقة (أسفل إلى أعلى bottom up).

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<stdio.h> 

// دالة مساعدة تعيد أكبر قيمة من بين القيمتين المعطاتين
int max(int a, int b) { return (a > b)? a : b; } 

// W تعيد الدالة أكبر قيمة يمكن وضعها في الحقيبة ذات السعة 
int knapSack(int W, int wt[], int val[], int n) 
{ 
int i, w; 
int K[n+1][W+1]; 

// إنشاء المصفوفة من الأسفل إلى الأعلى
for (i = 0; i <= n; i++) 
{ 
	for (w = 0; w <= W; w++) 
	{ 
		if (i==0 || w==0) 
			K[i][w] = 0; 
		else if (wt[i-1] <= w) 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); 
		else
				K[i][w] = K[i-1][w]; 
	} 
} 

return K[n][W]; 
} 

// اختبار الدالتين السابقتين
int main() 
{ 
	int val[] = {60, 100, 120}; 
	int wt[] = {10, 20, 30}; 
	int W = 50; 
	int n = sizeof(val)/sizeof(val[0]); 
	printf("%d", knapSack(W, wt, val, n)); 
	return 0; 
}

• بايثون:

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	# إنشاء المصفوفة من الأسفل إلى الأعلى 
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 

# اختبار الدالتين السابقتين
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
print(knapSack(W, wt, val, n))

• جافا:

class Knapsack 
{ 

	// تابع مساعد تعيد أكبر قيمة من بين القيمتين المعطاتين
	static int max(int a, int b) { return (a > b)? a : b; } 
	
    // W يعيد التابع أكبر قيمة يمكن وضعها في الحقيبة ذات السعة 
	static int knapSack(int W, int wt[], int val[], int n) 
	{ 
		int i, w; 
	int K[][] = new int[n+1][W+1]; 
	
	// إنشاء المصفوفة من الأسفل إلى الأعلى
	for (i = 0; i <= n; i++) 
	{ 
		for (w = 0; w <= W; w++) 
		{ 
			if (i==0 || w==0) 
				K[i][w] = 0; 
			else if (wt[i-1] <= w) 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); 
			else
				K[i][w] = K[i-1][w]; 
		} 
	} 
	
	return K[n][W]; 
	} 

	
	// اختبار التابعين السابقين
	public static void main(String args[]) 
	{ 
		int val[] = new int[]{60, 100, 120}; 
	int wt[] = new int[]{10, 20, 30}; 
	int W = 50; 
	int n = val.length; 
	System.out.println(knapSack(W, wt, val, n)); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة البرمجة الديناميكية المقدار O(nW)‎ وتمثّل n عدد العناصر المتوفرة وW سعة حقيبة الظهر.

مصادر

• صفحة 0-1 Knapsack Problem في توثيق الخوارزميات في موقع GeeksforGeeks.