مشكلة الحقيبة (Knapsack Problem) في الخوارزميات: شرح مبسّط مع أمثلة وطرق الحل

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

قبل أي شيء، تصحيح شائع: الاسم العربي الصحيح هو «مشكلة الحقيبة» أو «مشكلة حقيبة الظهر»، وليس «مشكلة الظهور» كما يتردد في بعض المواقع، فهي ترجمة حرفية خاطئة لكلمة Knapsack التي تعني الحقيبة. الأهم من الاسم هو فهم الفكرة، وهذا ما سنبنيه خطوة بخطوة.

لماذا تُعدّ مشكلة أساسية؟

مشكلة الحقيبة نموذج تعليمي مثالي لأنها تجمع بين مفهومين مركزيين في الخوارزميات: الطمع (Greedy) والبرمجة الديناميكية (Dynamic Programming). كما أنها من فئة مسائل التحسين التوافقي (Combinatorial Optimization)، ونسختها الأصعب (0/1) تُصنَّف ضمن مسائل NP-Complete، أي لا نعرف حتى اليوم خوارزمية سريعة (زمن كثير الحدود بالمعنى الدقيق) تحلّها لأي حجم مهما كبر.

أنواع مشكلة الحقيبة

1. الحقيبة 0/1 (0/1 Knapsack)

كل عنصر إمّا أن تأخذه كاملًا أو تتركه، ولا يمكن أخذ جزء منه. الرقمان 0 و1 يرمزان لهذا القرار الثنائي: خُذ (1) أو اترك (0). هذا هو النوع الأصعب والأكثر واقعية، لأن معظم الأشياء في الواقع لا تتجزأ (لا يمكنك أخذ «نصف حاسوب محمول»).

2. الحقيبة الكسرية (Fractional Knapsack)

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

وجه المقارنة	الحقيبة 0/1	الحقيبة الكسرية
تجزئة العنصر	غير مسموحة	مسموحة
أفضل طريقة حل	البرمجة الديناميكية	الخوارزمية الجشعة
هل الطمع يعطي الحل الأمثل؟	لا	نعم
التصنيف	NP-Complete	يُحل في زمن O(n log n)
مثال واقعي	اختيار مشاريع للتمويل	تحميل شاحنة برمل أو حبوب

كيف نحلّها؟

الخوارزمية الجشعة (للنسخة الكسرية)

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

تحذير مهم: الطمع نفسه يفشل في النسخة 0/1. لنرَ مثالًا: حقيبة سعتها 10، وأمامنا:

• عنصر A: وزن 5، قيمة 60
• عنصر B: وزن 3، قيمة 50
• عنصر C: وزن 4، قيمة 70

الطمع يبدأ بالأعلى نسبة (C ثم B) فيصل إلى قيمة 120 فقط. لكن الاختيار الأمثل فعلًا هو A + C بوزن 9 وقيمة 130. هنا يظهر لماذا نحتاج أداة أقوى.

البرمجة الديناميكية (للنسخة 0/1)

نبني جدولًا صفوفه تمثّل العناصر وأعمدته تمثّل كل سعة ممكنة من 0 إلى الوزن الأقصى. لكل خانة نسأل سؤالًا واحدًا: هل أضمّ هذا العنصر أم لا؟ ونأخذ الأفضل بين الخيارين:

dp[i][w] = max( dp[i-1][w] , value[i] + dp[i-1][w - weight[i]] )

الجزء الأول يعني «تجاهل العنصر»، والجزء الثاني يعني «خُذه واجمع قيمته مع أفضل حل للسعة المتبقية». زمن التنفيذ O(n × W) حيث n عدد العناصر وW السعة. يُسمى هذا الزمن pseudo-polynomial لأنه يعتمد على قيمة W وليس على عدد أرقامها فقط.

النهج العودي (Recursive)

أبسط تصوّر ذهني: جرّب كل التوليفات الممكنة واختر الأفضل. لكنه بطيء جدًا بتعقيد أسّي O(2ⁿ)، ولا يصلح إلا لعدد صغير من العناصر أو لفهم المسألة قبل تحسينها بالحفظ (Memoization).

تطبيقات عملية

• إدارة الموارد والميزانيات: اختيار مشاريع أو استثمارات تعطي أعلى عائد ضمن ميزانية محدودة.
• الخدمات السحابية والشبكات: توزيع مهام على خوادم بسعة معالجة أو ذاكرة محدودة.
• الشحن والخدمات اللوجستية: تعبئة حاويات أو طرود بأعلى قيمة ضمن حدّ وزن.
• التشفير: استُخدمت نسخ من المسألة تاريخيًا في أنظمة تشفير المفتاح العام مثل Merkle–Hellman.
• إدارة المحافظ المالية: انتقاء أصول ضمن سقف مخاطرة أو رأس مال محدد.

نصيحة عملية وخطأ شائع

الخطأ الأكثر شيوعًا عند المبتدئين هو تطبيق الحل الجشع على النسخة 0/1 لأنه «يبدو منطقيًا»، ثم الحصول على نتيجة قريبة لكنها غير مثالية. القاعدة الذهبية: إن كان العنصر غير قابل للتجزئة، استخدم البرمجة الديناميكية، لا الطمع. ونصيحة إضافية: إذا كانت السعة W ضخمة جدًا، فجدول البرمجة الديناميكية قد يستهلك ذاكرة هائلة، وعندها يُفضَّل حلول تقريبية (Approximation) أو خوارزمية FPTAS التي تعطي نتيجة قريبة من المثالية بزمن معقول.

الأسئلة الشائعة

هل مشكلة الحقيبة قابلة للحل دائمًا؟ نعم، يوجد حل مثالي دائمًا، لكن إيجاده للنسخة 0/1 قد يستغرق زمنًا كبيرًا جدًا مع تزايد عدد العناصر لأنها من فئة NP-Complete.

ما الفرق الجوهري بين النسختين 0/1 والكسرية؟ الكسرية تسمح بأخذ أجزاء من العناصر ويحلّها الطمع حلًّا مثاليًا، أما 0/1 فقرارها ثنائي (خُذ أو اترك) وتحتاج البرمجة الديناميكية.

لماذا لا نستخدم الطمع دائمًا لأنه أسرع؟ لأنه لا يضمن الحل الأمثل في النسخة 0/1؛ قد يعطي قيمة أقل من الحل الحقيقي كما رأينا في المثال الرقمي أعلاه.

ما تعقيد البرمجة الديناميكية لهذه المسألة؟ O(n × W)، وهو زمن pseudo-polynomial يعتمد على عدد العناصر وقيمة السعة معًا، وليس سريعًا فعليًا حين تكون السعة كبيرة جدًا.