مسألة الحقيبة الكسرية

تتشابه مسألة الحقيبة الكسرية إجمالاً كثيراً مع مسألة حقيبة 0-1، حيث تتضمن الحالات العنصر الحالي $i$ والسعة $c$، والهدف هو تعظيم القيمة في حدود سعة الحقيبة المحدودة.

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

1. بالنسبة إلى العنصر $i$، قيمته لكل وحدة وزن هي $val[i-1] / wgt[i-1]$، وتسمى القيمة الوحدية.
2. لنفترض أننا وضعنا في الحقيبة جزءاً من العنصر $i$ وزنه $w$، فإن القيمة المضافة إلى الحقيبة هي $w \times val[i-1] / wgt[i-1]$.

تحديد الاستراتيجية الجشعة

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

1. رتّب العناصر حسب القيمة الوحدية من الأعلى إلى الأدنى.
2. اجتَز جميع العناصر، واختر جشعاً في كل جولة العنصر ذا القيمة الوحدية الأعلى.
3. إذا لم تكفِ سعة الحقيبة المتبقية، فاستخدم جزءاً من العنصر الحالي لملء الحقيبة.

تنفيذ الشيفرة

نعرّف صنف Item بحيث يمكن ترتيب العناصر حسب القيمة الوحدية. ثم نجتاز العناصر المرتبة جشعاً، ونتوقف بمجرد امتلاء الحقيبة ونعيد النتيجة:

/* الحقيبة الكسرية: خوارزمية جشعة */
func fractionalKnapsack(wgt []int, val []int, cap int) float64 {
	// أنشئ قائمة العناصر بسمتين: الوزن والقيمة
	items := make([]Item, len(wgt))
	for i := 0; i < len(wgt); i++ {
		items[i] = Item{wgt[i], val[i]}
	}
	// رتّب حسب القيمة الوحدية item.v / item.w من الأعلى إلى الأدنى
	sort.Slice(items, func(i, j int) bool {
		return float64(items[i].v)/float64(items[i].w) > float64(items[j].v)/float64(items[j].w)
	})
	// حلقة الاختيار الجشع
	res := 0.0
	for _, item := range items {
		if item.w <= cap {
			// إذا كانت السعة المتبقية كافية، ضع العنصر الحالي كاملاً في الحقيبة
			res += float64(item.v)
			cap -= item.w
		} else {
			// إذا لم تكن السعة المتبقية كافية، ضع جزءاً من العنصر الحالي في الحقيبة
			res += float64(item.v) / float64(item.w) * float64(cap)
			// لا توجد سعة متبقية، لذا اخرج من الحلقة
			break
		}
	}
	return res
}

/* الحقيبة الكسرية: خوارزمية جشعة */
function fractionalKnapsack(wgt: number[], val: number[], cap: number): number {
    // أنشئ قائمة العناصر بسمتين: الوزن والقيمة
    const items: Item[] = wgt.map((w, i) => new Item(w, val[i]));
    // رتّب حسب القيمة الوحدية item.v / item.w من الأعلى إلى الأدنى
    items.sort((a, b) => b.v / b.w - a.v / a.w);
    // حلقة الاختيار الجشع
    let res = 0;
    for (const item of items) {
        if (item.w <= cap) {
            // إذا كانت السعة المتبقية كافية، ضع العنصر الحالي كاملاً في الحقيبة
            res += item.v;
            cap -= item.w;
        } else {
            // إذا لم تكن السعة المتبقية كافية، ضع جزءاً من العنصر الحالي في الحقيبة
            res += (item.v / item.w) * cap;
            // لا توجد سعة متبقية، لذا اخرج من الحلقة
            break;
        }
    }
    return res;
}

تستغرق خوارزميات الترتيب المدمجة عادةً زمن $O(n \log n)$، ويكون تعقيدها المكاني عادةً $O(\log n)$ أو $O(n)$، حسب التنفيذ المحدد للغة البرمجة.

وفيما عدا الترتيب، يجب في أسوأ الحالات اجتياز قائمة العناصر كاملة، لذا فإن التعقيد الزمني هو $O(n)$، حيث $n$ عدد العناصر.

وبما أنه تُهيَّأ قائمة من كائنات Item، فإن التعقيد المكاني هو $O(n)$.

إثبات الصحة

نستخدم البرهان بالتناقض. لنفترض أن العنصر $x$ ذو القيمة الوحدية الأعلى، وأن خوارزمية ما تنتج قيمة مثلى res، لكن الحل الناتج لا يتضمن العنصر $x$.

الآن أزل وحدة وزن واحدة من أي عنصر في الحقيبة، واستبدلها بوحدة وزن واحدة من العنصر $x$. وبما أن العنصر $x$ ذو القيمة الوحدية الأعلى، فلا بد أن تكون القيمة الإجمالية بعد الاستبدال أكبر من res. وهذا يناقض افتراض أن res مثلى، مما يثبت أن أي حل أمثل لا بد أن يتضمن العنصر $x$.

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

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