55. مثال DP 3: مشكلة حقيبة الظهر (Knapsack) (مقدمة 0/1)

مشكلة حقيبة الظهر 0/1 (The 0/1 Knapsack Problem)

لديك حقيبة ظهر (Knapsack) بسعة قصوى للوزن W. لديك مجموعة من N من العناصر، لكل منها وزن محدد وقيمة محددة. يجب أن تقرر، لكل عنصر، ما إذا كنت ستأخذه (1) أو تتركه (0). الهدف هو تعظيم القيمة الإجمالية دون تجاوز السعة W.

لماذا DP؟

تتميز هذه المشكلة بكل من البنية المثلى (Optimal Substructure) (يعتمد أفضل حل لسعة w على أفضل حل لسعات أقل من w) و المشكلات الفرعية المتداخلة (Overlapping Subproblems).

تعريف حالة DP

نحدد جدول DP ثنائي الأبعاد: DP[i][w] = أقصى قيمة يمكن تحقيقها باستخدام أول i من العناصر بسعة حقيبة ظهر w.

لكل عنصر i وسعة w، نقرر:

1. عدم تضمين العنصر i: DP[i-1][w]
2. تضمين العنصر i: value[i] + DP[i-1][w - weight[i]]

نختار الحد الأقصى من هذين الخيارين. هذا الملء التكراري لجدول DP يحل المشكلة المعقدة بكفاءة.