مسألة حقيبة الظهر

مسألة حقيبة الظهر هي مسألة تدخل في إطار الاستمثال التوافقي."Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM’14, 2427–2435.  فإذا كانت لدينا مجموعة من العناصر، لكل منها وزن و قيمة، فعليك أن تحدد العناصر التي تُدرج في الحقيبة، بحيث يكون مجموع أوزانها أقل من أو يساوي قدراً معيناً، وأن يكون مجموع القيم أعلى ما يكون.
اسم هذه المسألة مأخوذ من حالة شخص ما لديه حقيبة ذات حجم محدد، وعليه أن يعبئها بالعناصر الأعلى قيمةً.

تم تناول هذه المسألة منذ أكثر من قرن، وليس من المعروف كيف نشأ تعبير (مسألة حقيبة الظهر)، رغم أنه تم ذكرها في أعمال العالم الرياضي توبياس دانزج (1844-1956)، وهو من اقترح أن الاسم ربما قد يكون نشأ في التراث الشعبي قبل أن تتم نمذجة المسألة رياضياً.

 التطبيقات 

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

من أقدم تطبيقات هذه المسألة هو إنشاء وتقييم الامتحانات ذات الأسئلة الاختيارية. في هذه الامتحانات يمكن للطالب أن يختار أي مجموعة من الأسئلة يريد إجابتها، وبحيث يستهدف الحصول على الدرجة النهائية. فمثلاً في حالة كون الامتحان محتوياً على 12 سؤالاً، لكل منها 10 درجات، يسهل على الطالب معرفة أنه يحتاج لإجابة 10 أسئلة فقط للحصول على الدرجة النهائية (100 درجة). لكن لو احتوى الامتحان على أسئلة ذات درجات متفاوتة، لأصبح الاختيار أصعب، ولاحتاج الأمر لخوارزم (مسألة حقيبة الظهر) لتحديد مجموعة الأسئلة التي يمكن للطالب أن يجيبها ليحصل على الدرجة النهائية.
 انظر أيضا 
 مشكلة إعادة جدولة السيارة

 مراجع 

تصنيف:استمثال توافقي
تصنيف:برمجة خطية
تصنيف:برمجة ديناميكية
تصنيف:تعمية
تصنيف:مسائل كثيرة حدود غير قطعية كاملة