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

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

جدول صفوفه أغراض وأعمدته سعات، ومسار التتبع العكسي باللون البرتقالي، بجانب حقيبة وأغراض بأحجام مختلفة
جدول صفوفه أغراض وأعمدته سعات، ومسار التتبع العكسي باللون البرتقالي، بجانب حقيبة وأغراض بأحجام مختلفة

المسألة

لدينا n من الأغراض، لكل منها وزن وقيمة، وحقيبة تتسع لوزن W على الأكثر. اختر مجموعة من الأغراض مجموع أوزانها W على الأكثر ومجموع قيمها أكبر ما يمكن. كل غرض يدخل كاملًا أو يبقى خارجًا، ولهذا تُسمى مسألة حقيبة الظهر 0/1. مع n من الأغراض توجد 2ⁿ مجموعة ممكنة، لذا تصبح تجربتها كلها مستحيلة سريعًا.

الجدول

لتكن best[i][w] أكبر قيمة تتسع في الوزن w باستخدام أول i من الأغراض فقط. عندئذ best[0][w] = 0، ولكل صف لاحق خياران: ترك الغرض i خارجًا، مما يعطي best[i − 1][w]، أو إن كان وزنه wᵢ يتسع، وضعه في الحقيبة، مما يعطي قيمته زائد best[i − 1][w − wᵢ]. والأكبر منهما هو best[i][w]. ملء الجدول صفًا بعد صف يضمن أن الخليتين اللتين يحتاجهما جاهزتان دائمًا.

مثال

خذ سعة 7 وأربعة أغراض أوزانها 1 و3 و4 و5 وقيمها 1 و4 و5 و7. مع الغرض الأول وحده، قيمة كل سعة من 1 فما فوق هي 1. بإضافة الثاني، تتسع السعة 4 للاثنين معًا بقيمة 5. بإضافة الثالث، تتسع السعة 7 للغرضين 2 و3 بقيمة 9. الغرض الرابع، ووزنه 5 وقيمته 7، يمكن أن ينضم إلى الغرض 1 فيعطي 8 عند السعة 6 أو 7، لكن 9 أفضل، لذا الخلية السفلية اليمنى هي 9: ضع في الحقيبة الغرضين اللذين وزنهما 3 و4.

ما مدى صعوبتها؟

يحتاج الجدول إلى نحو n·W خطوة. يبدو هذا سريعًا، لكن W عدد، والعدد ذو d من الأرقام قد يبلغ 10 أس d، لذا ينمو العمل أسيًا مع طول المدخلات. مسألة حقيبة الظهر NP-صعبة؛ وكانت إحدى مسائل NP-التامة الـ21 التي حددها ريتشارد كارب عام 1972. وفي التطبيق العملي، تتعامل طريقة الجدول وطريقة التفرع والتقييد ومخططات التقريب الجيدة مع الحالات الحقيقية الكبيرة بكفاءة.

التاريخ والاستخدامات

يعود الاسم إلى عالم الرياضيات توبياس دانتزيغ في أوائل القرن العشرين، وقدّم ابنه جورج دانتزيغ طريقة جشعة كلاسيكية لها عام 1957. تظهر مسائل حقيبة الظهر في إعداد الميزانيات واختيار المحافظ الاستثمارية، وفي قطع المواد الخام بأقل هدر ممكن، وفي تحميل البضائع، بل حتى في التشفير بالمفتاح العام في بداياته: فقد بُني نظام التشفير ميركل–هيلمان عام 1978 على مسألة حقيبة الظهر، ثم كُسر بعد بضع سنوات.

جورج دانتزيغ (يسار) يتسلم الميدالية الوطنية للعلوم من الرئيس جيرالد فورد عام 1976. في عام 1957 قدّم دانتزيغ أسلوباً جشعاً كلاسيكياً لمسألة الحقيبة. ويعود الاسم نفسه إلى أبيه توبياس دانتزيغ.
جورج دانتزيغ (يسار) يتسلم الميدالية الوطنية للعلوم من الرئيس جيرالد فورد عام 1976. في عام 1957 قدّم دانتزيغ أسلوباً جشعاً كلاسيكياً لمسألة الحقيبة. ويعود الاسم نفسه إلى أبيه توبياس دانتزيغ.

استكشفها

افتح التطبيق، وانتقل إلى عرض «الجدول»، واضغط «خطوة». الخلية البرتقالية هي التي تُملأ، والخليتان الزرقاوان هما اللتان تقارن بينهما: الخلية التي فوقها مباشرة، والخلية في الصف الذي فوقها إلى اليسار بمقدار وزن الغرض. بعد آخر خلية، يصعد التتبع العكسي من الزاوية السفلية اليمنى باللون البرتقالي، وتظهر الأغراض المعبأة تحت الجدول.

الأسئلة المتداولة

ما الفرق بين حقيبة الظهر 0/1 والمحدودة وغير المحدودة؟

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

هل تكون الطريقة الجشعة صحيحة أحيانًا في حقيبة الظهر؟

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

كم من الذاكرة يحتاج الجدول؟

(n + 1)·(W + 1) خلية للجدول الكامل، وهو ما تحتاجه لتتبع الأغراض عكسيًا. وإن كانت أفضل قيمة وحدها هي المطلوبة، فيكفي صف واحد من W + 1 خلية يُملأ من اليمين إلى اليسار.

هل حقيبة الظهر هي نفسها مسألة مجموع المجموعة الجزئية؟

مجموع المجموعة الجزئية حالة خاصة تساوي فيها قيمة كل غرض وزنه، والسؤال هو هل يمكن ملء الحقيبة تمامًا. وهي أيضًا NP-تامة وتُحل بالنوع نفسه من الجداول.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

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