مسألة حقيبة الظهر هي مسألة تدخل في إطار الاستمثال التوافقي.[1][2][3] فإذا كانت لدينا مجموعة من العناصر، لكل منها وزن و قيمة، فعليك أن تحدد العناصر التي تُدرج في الحقيبة، بحيث يكون مجموع أوزانها أقل من أو يساوي قدراً معيناً، وأن يكون مجموع القيم أعلى ما يكون. اسم هذه المسألة مأخوذ من حالة شخص ما لديه حقيبة ذات حجم محدد، وعليه أن يعبئها بالعناصر الأعلى قيمةً.
تم تناول هذه المسألة منذ أكثر من قرن، وليس من المعروف كيف نشأ تعبير (مسألة حقيبة الظهر)، رغم أنه تم ذكرها في أعمال العالم الرياضي توبياس دانزج (1844-1956)، وهو من اقترح أن الاسم ربما قد يكون نشأ في التراث الشعبي قبل أن تتم نمذجة المسألة رياضياً.
التطبيقات
مبداً المشكلة متعلق بتخصيص المصادر، ولمسألة حقيبة الظهر عدة تطبيقات في عمليات اتخاذ القرار، ومنها: إيجاد أفضل طريقة لتقطيع خامة، إيجاد أفضل طريقة لتعبئة حاوية، الاختيار بين بدائل الاستثمار والمحافظ المالية مع عدم تخطي سقف معين للمبلغ المراد استثماره.
من أقدم تطبيقات هذه المسألة هو إنشاء وتقييم الامتحانات ذات الأسئلة الاختيارية. في هذه الامتحانات يمكن للطالب أن يختار أي مجموعة من الأسئلة يريد إجابتها، وبحيث يستهدف الحصول على الدرجة النهائية. فمثلاً في حالة كون الامتحان محتوياً على 12 سؤالاً، لكل منها 10 درجات، يسهل على الطالب معرفة أنه يحتاج لإجابة 10 أسئلة فقط للحصول على الدرجة النهائية (100 درجة). لكن لو احتوى الامتحان على أسئلة ذات درجات متفاوتة، لأصبح الاختيار أصعب، ولاحتاج الأمر لخوارزم (مسألة حقيبة الظهر) لتحديد مجموعة الأسئلة التي يمكن للطالب أن يجيبها ليحصل على الدرجة النهائية.
مقالات ذات صلة
مراجع
- Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Unbounded Knapsack Problem : dynamic programming revisited". European Journal of Operational Research. 123 (2): 168–181. doi:10.1016/S0377-2217(99)00265-9. مؤرشف من الأصل في 29 يناير 2020.
- Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "The Multiple Subset Sum Problem". SIAM J. on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. مؤرشف من الأصل في 21 يوليو 2018.
- "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM’14, 2427–2435. نسخة محفوظة 09 أغسطس 2017 على موقع واي باك مشين.