Algorithms/fractional knapsack

المطلوب في مسألة حقيبة الظهر المجزّأة Fractional Knapsack هو وضع مجموعة من العناصر ذات أوزان وقيم محددة في حقيبة ظهر تتسع لعدد معين من العناصر مع مراعاة الحصول على أكبر قيمة ممكنة لمجموع قيم العناصر الموجودة في الحقيبة.

يسمح في مسألة حقيبة الظهر المجزّأة بتقسيم العناصر للحصول على أكبر قيمة ممكنة لمجموع قيم العناصر.

مثال:

المدخلات : 
العناصر على هيئة أزواج (قيمة، وزن)
  arr[] = {{60, 10}, {100, 20}, {120, 30}}
المخرجات :
   أكبر قيمة ممكنة = 240
   وذلك بأخذ العنصرين ذوي الوزنين 10 و 20 كاملين
   وأخذ ثلثي العنصر الأخير ذي الوزن 30

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

مثال:

المدخلات:
  العناصر على هيئة أزواج (قيمة، وزن)
  arr[] = {{60, 10}, {100, 20}, {120, 30}}
  سعة الحقيبة W = 50
المخرجات:
  أكبر قيمة ممكنة = 220
  وذلك بوضع العنصرين ذوي الوزنين 20 و 30

خطوات الخوارزمية

يمكن حلّ هذه المسألة بأسلوب القوة الغاشمة Brute force وذلك بتجربة جميع المجاميع الفرعية المحتملة مع جميع الأجزاء المختلفة، ولكن تستغرق هذه الطريقة الكثير من الوقت.

يبتع الحل الأمثل لهذه المسألة أسلوب الخوارزميات الجشعة، وذلك بحساب النسبة قيمة\وزن لكل عنصر ثم ترتيب العناصر بالاعتماد على هذه النسبة. تأخذ الخوارزمية بعد ذلك العناصر ذات النسبة الأعلى وتجمعها مع بعضها إلى أن تصل إلى المرحلة التي لا يمكن فيها إضافة العنصر التالي كاملًا، وفي النهاية تضيف الخوارزمية النسبة الممكنة من العنصر التالي، والنتيجة هي الحصول على الحل الأمثل لهذه المسألة دائمًا.

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

تستخدم الشيفرات التالية دالة بسيطة للمقارنة بين نسب العنصار، والمعامل الثالث في دالة الترتيب هو دالة المقارنة التي ترتب العناصر حسب نسبة القيمة\الوزن ترتيبًا تصاعديًا.

تضاف العناصر إلى الحقيبة وفق شروط المسألة بعد المرور على جميع العناصر.

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

• C++:

#include <bits/stdc++.h> 

using namespace std; 

// تستخدم هذه البنية لتخزين وزن وقيمة العنصر
struct Item 
{ 
	int value, weight; 

	// دالة بانية
	Item(int value, int weight) : value(value), weight(weight) 
	{} 
}; 

// دالة المقارنة لترتيب العناصر وفق نسبة القيمة\الوزن
bool cmp(struct Item a, struct Item b) 
{ 
	double r1 = (double)a.value / a.weight; 
	double r2 = (double)b.value / b.weight; 
	return r1 > r2; 
} 

// الدالة الرئيسية التي تحلّ المسألة بأسلوب الخوارزميات الجشعة
double fractionalKnapsack(int W, struct Item arr[], int n) 
{ 
	// ترتيب العناصر وفق النسبة
	sort(arr, arr + n, cmp); 

	// يمكن إلغاء تعليق الكتلة لمشاهدة ترتيب العناصر الجديد
	/* 
	for (int i = 0; i < n; i++) 
	{ 
		cout << arr[i].value << " " << arr[i].weight << " : " 
			<< ((double)arr[i].value / arr[i].weight) << endl; 
	} 
	*/

	int curWeight = 0; // الوزن الحالي في الحقيبة
	double finalvalue = 0.0; // النتيجة (القيمة في الحقيبة)

	// المرور على جميع العناصر
	for (int i = 0; i < n; i++) 
	{ 
		// يضاف العنصر الحالي إن لم يكن وزنه زائدًا عن سعة الحقيبة
		if (curWeight + arr[i].weight <= W) 
		{ 
			curWeight += arr[i].weight; 
			finalvalue += arr[i].value; 
		} 

		// إن لم يكن بالإمكان إضافة العنصر الحالي كاملًا، يُضاف جزء منه
		else
		{ 
			int remain = W - curWeight; 
			finalvalue += arr[i].value * ((double) remain / arr[i].weight); 
			break; 
		} 
	} 

	// إعادة القيمة النهائية
	return finalvalue; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int W = 50; // سعة الحقيبة
	Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; 

	int n = sizeof(arr) / sizeof(arr[0]); 

	cout << "Maximum value we can obtain = "
		<< fractionalKnapsack(W, arr, n); 
	return 0; 
}

• بايثون:

class ItemValue: 
	
	""" معلومات العنصر """
	def __init__(self, wt, val, ind): 
		self.wt = wt 
		self.val = val 
		self.ind = ind 
		self.cost = val // wt 

	def __lt__(self, other): 
		return self.cost < other.cost 

# أسلوب الخوارزمية الجشعة
class FractionalKnapSack: 
	# O(nlogn) التعقيد الزمني هو 
	@staticmethod
	def getMaxValue(wt, val, capacity): 
		
		# تجلب الدالة القيمة الأكبر
		iVal = [] 
		for i in range(len(wt)): 
			iVal.append(ItemValue(wt[i], val[i], i)) 

		# ترتيب العناصر وفقًا لقيمتها
		iVal.sort(reverse = True) 

		totalValue = 0
		for i in iVal: 
			curWt = int(i.wt) 
			curVal = int(i.val) 
			if capacity - curWt >= 0: 
				capacity -= curWt 
				totalValue += curVal 
			else: 
				fraction = capacity / curWt 
				totalValue += curVal * fraction 
				capacity = int(capacity - (curWt * fraction)) 
				break
		return totalValue 

# اختبار الدالة السابقة 
if __name__ == "__main__": 
	wt = [10, 40, 20, 30] 
	val = [60, 40, 100, 120] 
	capacity = 50

	maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity) 
	print("Maximum value in Knapsack =", maxValue)

• جافا:

import java.util.Arrays; 
import java.util.Comparator; 

// أسلوب الخوارزمية الجشعة
public class FractionalKnapSack 
{ 
	// O(nlogn) التعقيد الزمني هو 
	public static void main(String[] args) 
	{ 
		int[] wt = {10, 40, 20, 30}; 
		int[] val = {60, 40, 100, 120}; 
		int capacity = 50; 

		double maxValue = getMaxValue(wt, val, capacity); 
		System.out.println("Maximum value we can obtain = " + 
							maxValue); 

	} 

	// تجلب الدالة القيمة الأكبر
	private static double getMaxValue(int[] wt, 
						int[] val, int capacity) 
	{ 
		ItemValue[] iVal = new ItemValue[wt.length]; 

		for(int i = 0; i < wt.length; i++) 
		{ 
			iVal[i] = new ItemValue(wt[i], val[i], i); 
		} 

		// ترتيب العناصر وفقًا لقيمتها
		Arrays.sort(iVal, new Comparator<ItemValue>() 
		{ 
			@Override
			public int compare(ItemValue o1, ItemValue o2) 
			{ 
				return o2.cost.compareTo(o1.cost) ; 
			} 
		}); 


		double totalValue = 0d; 

		for(ItemValue i: iVal) 
		{ 

			int curWt = (int) i.wt; 
			int curVal = (int) i.val; 

			if (capacity - curWt >= 0) 
			{ 
				// يمكن إضافة هذا العنصر كاملًا
				capacity = capacity-curWt; 
				totalValue += curVal; 

			} 
			else
			{ 
				// إضافة جزء من العنصر
				double fraction = ((double)capacity/(double)curWt); 
				totalValue += (curVal*fraction); 
				capacity = (int)(capacity - (curWt*fraction)); 
				break; 
			} 


		} 

		return totalValue; 
	} 

	// صنف لتمثيل قيمة العنصر
	static class ItemValue 
	{ 
		Double cost; 
		double wt, val, ind; 
		
		// دالة لتمثيل قيمة العنصر
		public ItemValue(int wt, int val, int ind) 
		{ 
			this.wt = wt; 
			this.val = val; 
			this.ind = ind; 
			cost = new Double(val/wt ); 
		} 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Maximum value in Knapsack = 240

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

تستهلك عملية ترتيب العناصر الجزء الأكبر من الوقت، لذا يمكن حل المسألة في تعقيد زمني قدره O(n log n)‎ فقط.

مصادر

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