مشكلة حقيبة الظهر الكسرية (Fractional Knapsack): شرح مبسّط بمثال محسوب

مشكلة حقيبة الظهر الكسرية (Fractional Knapsack Problem) هي مسألة تحسين كلاسيكية تسأل: لديك حقيبة تتحمّل وزنًا أقصى محدّدًا، ومجموعة من العناصر لكلٍّ منها وزن وقيمة، فكيف تملؤها لتحصل على أعلى قيمة إجمالية ممكنة؟ ما يميّزها عن غيرها أنّك مسموح لك بأخذ جزء من أي عنصر لا العنصر كاملًا. والخبر الجميل أنّ لها حلًّا بسيطًا ومثاليًا مضمونًا عبر ما يُعرف بالخوارزمية الجشعة (Greedy Algorithm)، وهذا ما يجعلها من أوائل ما يُدرَّس في مساقات الخوارزميات.

الفكرة الجوهرية التي تحلّ المسألة كلها: رتّب العناصر حسب القيمة لكل وحدة وزن (الكثافة = القيمة ÷ الوزن)، ثم املأ الحقيبة بالأعلى كثافةً أولًا. وحين تصل إلى عنصر لا تتّسع الحقيبة له بالكامل، خذ منه كسرًا يملأ ما تبقّى تمامًا.

المصطلحات الأساسية بسرعة

• السعة (Capacity / W): أقصى وزن تتحمّله الحقيبة.
• الوزن (weight): كم يشغل العنصر من هذه السعة.
• القيمة (value): العائد الذي نريد تعظيمه.
• الكثافة (value/weight): القيمة مقابل كل كيلوغرام أو وحدة وزن. هذا هو المعيار الذي نرتّب عليه، وليس القيمة وحدها ولا الوزن وحده.

مثال محسوب خطوة بخطوة

لنفترض أنّ سعة الحقيبة 50، ولدينا ثلاثة عناصر:

العنصر	القيمة	الوزن	القيمة/الوزن
A	60	10	6.0
B	100	20	5.0
C	120	30	4.0

نرتّب تنازليًا حسب الكثافة: A ثم B ثم C.

1. العنصر A: كثافته الأعلى (6). نأخذه كاملًا. الوزن المستهلك = 10، القيمة المجمّعة = 60، والمتبقّي من السعة = 40.
2. العنصر B: نأخذه كاملًا. الوزن المستهلك يصبح 30، القيمة = 160، والمتبقّي = 20.
3. العنصر C: وزنه 30 لكن تبقّى لنا 20 فقط. نأخذ كسرًا منه = 20 ÷ 30 = ثُلثين، فتضيف قيمة = 120 × (2/3) = 80.

القيمة الإجمالية النهائية = 60 + 100 + 80 = 240. لا يوجد ترتيب آخر يعطي أفضل من ذلك، وهذا ما تضمنه الطريقة الجشعة في هذه المسألة تحديدًا.

خطوات الخوارزمية بشكل عام

1. احسب الكثافة (القيمة ÷ الوزن) لكل عنصر.
2. رتّب العناصر تنازليًا حسب هذه الكثافة.
3. مُرّ على العناصر بالترتيب: إن اتّسعت الحقيبة للعنصر كاملًا فخذه كاملًا واطرح وزنه من السعة المتبقّية.
4. عند أول عنصر لا يتّسع بالكامل، خذ منه الكسر الذي يملأ المتبقّي تمامًا، ثم توقّف.

التعقيد الزمني: الترتيب هو الخطوة الأغلى، لذا الخوارزمية تعمل بزمن O(n log n) حيث n عدد العناصر. المرور والتعبئة نفسه لا يتجاوز O(n).

لماذا تنجح الطريقة الجشعة هنا؟

لأنّ إمكانية التقسيم تجعل المسألة "متّصلة" لا "تجميعية". كل وحدة وزن يمكن استبدالها بحرية، فمن المنطقي دائمًا أن تُملأ السعة بالوحدات الأغلى قيمةً أولًا؛ لن تندم أبدًا على أخذ وحدة أعلى كثافة قبل أخرى أقل. هذا البرهان (يُسمّى برهان التبادل / exchange argument) لا يصمد في النسخة الأخرى.

الفرق عن مشكلة 0/1 Knapsack

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

الوجه	Fractional	0/1
تقسيم العنصر	مسموح	ممنوع
الخوارزمية المثلى	جشعة (Greedy)	برمجة ديناميكية
هل الجشع يعطي الحل الأمثل؟	نعم دائمًا	لا، قد يفشل
التعقيد	O(n log n)	O(n·W) (شبه كثير حدود)
طبيعة المسألة	متّصلة/سهلة	تجميعية/أصعب (NP-hard)

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

خطأ شائع ونصيحة عملية

الخطأ الأكثر تكرارًا عند المبتدئين هو الترتيب حسب القيمة الأعلى أو الوزن الأقل بدل الكثافة. عنصر قيمته 120 قد يبدو الأجذب، لكنه إن كان ثقيلًا جدًا فربّما يخسّرك قيمةً أكبر كان يمكن جمعها من عناصر أخف وأعلى كثافة. القاعدة الذهبية: القرار دائمًا على أساس القيمة/الوزن، لا على القيمة المطلقة.

نصيحة عند البرمجة: احذر القسمة على وزن يساوي صفرًا (عنصر بلا وزن وله قيمة يجب أخذه أولًا بلا تكلفة)، واستخدم أعدادًا عشرية (float/double) لتخزين الكسر الناتج حتى لا تخسر دقة الحساب.

الأسئلة الشائعة

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

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

أين تُستخدم عمليًا؟ في تخصيص الموارد القابلة للتجزئة: توزيع ميزانية أو نطاق ترددي أو وقت معالجة على مهام متعددة، وتحسين استغلال مساحة تخزين أو شحنات يمكن تجزئتها.

متى لا تصلح هذه الطريقة؟ عندما لا يمكن تقسيم العنصر (سلعة واحدة، ملف كامل، شخص). حينها تكون المسألة 0/1 Knapsack، وتحتاج إلى البرمجة الديناميكية للوصول إلى الحل الأمثل.