كل ما تريد معرفته عن مسألة حقيبة الظهر

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

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

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

قراءة المقال الكامل على ويكيبيديا ←