Knapsack Problem

مسألة حقيبة الظهر (Knapsack Problem) هي مسألة التحسين المنفصل الكلاسيكيّة: لكلٍّ من N عنصر مرشّح قيمة (vᵢ) ووزن (wᵢ)، وتحت قيد سعة W الهدف max Σvᵢxᵢ بشرط Σwᵢxᵢ ≤ W. الاسم من استعارة ملء حقيبة محدودة السعة بأنفس الحمولة. أمثلة عمليّة: اختيار المجموعة الجزئية الأعلى NPV من المشاريع المرشّحة تحت ميزانية سنويّة ثابتة، اختيار الحملات تحت ميزانية ثابتة، شحن الطرود في طائرة شحن محدودة السعة، اختيار الأسهم الصغيرة في صندوق. النُسخ: 0/1 (ثنائي؛ xᵢ ∈ {0, 1})، bounded (xᵢ ∈ {0, ..., cᵢ})، unbounded (xᵢ ≥ 0 صحيح)، متعدّد الأبعاد (MKP — m قيد)، تربيعي (QKP — تآزر ثنائي)، multiple-choice (عنصر واحد لكلّ مجموعة)، subset-sum، knapsack مع set-up. Knapsack من فئة NP-hard، لكنّ البرمجة الديناميكية عند Bellman (1957) تحلّها في O(N×W) — **شبه متعدّدة الحدود** — وعند W معتدلة (آلاف-عشرات الآلاف) تتعامل مع نُسخ بملايين العناصر إلى الأمثل في دقائق. Branch-and-bound (Martello وToth 1990؛ Pisinger 1997 expanding-core)، MIP، FPTAS (Ibarra وKim 1975 — ضمان (1-ε)) هي الأدوات الكلاسيكيّة. مراجع كلاسيكيّة: Dantzig (1957) أوّل صياغة LP/IP، Martello وToth (1990) كتاب كلاسيكي، Kellerer وPferschy وPisinger (2004) مرجع حديث شامل. Portfolio Optimization (#018 Markowitz، أوزان متّصلة + تباين) وCutting Stock (#005، هندسي متعدّد الأبعاد) أقارب قريبون لكنّها مسائل مختلفة.