0/1 Knapsack Problem
لديك عدد n من العناصر. يزن العنصر i مقدار weights[i] وتبلغ قيمته values[i]. يمكن لحقيبتك حمل وزن إجمالي لا يتجاوز capacity. يوجد عنصر واحد من كل نوع، ويمكنك إما وضعه كاملًا في الحقيبة أو تركه. أعد أكبر قيمة إجمالية يمكنك وضعها في الحقيبة.
الدالة
- weightsinteger-array
- وزن كل عنصر
- valuesinteger-array
- قيمة كل عنصر
- capacityinteger
- أقصى وزن يمكن للحقيبة حمله
- تُرجعinteger
- أكبر قيمة إجمالية للعناصر التي تتسع أوزانها ضمن السعة
القيود
1 ≤ n ≤ 100، حيثn = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
أمثلة
- المدخلات
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- المخرجات
- 17
- الشرح
- يزن العنصران 0 و2 مقدار 4 + 3 = 7، وتبلغ قيمتهما 10 + 7 = 17. إن وضع العنصر الأعلى قيمة أولًا (الوزن 5، القيمة 12) لا يترك مجالًا إلا للعنصر 1، ليكون المجموع 16.
- المدخلات
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- المخرجات
- 13
- الشرح
- يزن العنصران 1 و2 مقدار 4 + 3 = 7، وتبلغ قيمتهما 7 + 6 = 13. يحقق العنصر 0 قيمة قدرها 2 لكل وحدة وزن، مثل أي عنصر آخر، لكن بعد وضعه لا تكفي الوحدتان المتبقيتان لأي شيء.
- المدخلات
- weights = [6, 8]values = [5, 9]capacity = 5
- المخرجات
- 0
- الشرح
- يزن كلا العنصرين أكثر من 5، لذا لا يتسع لهما شيء وتكون قيمة الحقيبة الفارغة 0.
سؤال إضافي
افترض أن السعة قد تصل إلى 10^9، بينما لا يتجاوز مجموع القيم 10^4. بماذا ستفهرس الجدول؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قرّر بشأن العناصر بالترتيب، بدءًا من العنصر 0. سواء أضفته إلى الحقيبة أم تركته، فستواجه السؤال نفسه بشأن العناصر التي تليه. ما الرقم الذي يتغير في ذلك السؤال؟
تعتمد أفضل قيمة من الآن فصاعدًا على رقمين فقط: العنصر الذي تنظر إليه والمساحة المتبقية. مع 100 عنصر وسعة قدرها 1000، يوجد نحو 10^5 من هذه الأزواج، لذا يمكنك حساب قيمة كل زوج مرة واحدة وتخزينها.
احتفظ بـ
best[c]لكل سعةcمن 0 إلىcapacity، واجعلها كلها 0 في البداية. لكل عنصر وزنهwوقيمتهv، مرّ علىcتنازليًا منcapacityإلىwواحتفظ بالقيمة الأكبر بينbest[c]وbest[c-w] + v. يمنع المرور تنازليًا تعبئة العنصر مرتين.
الحل
لا ينجح أي ترتيب جشع: فاختيار العنصر الأعلى قيمةً أولًا يعطي 16، وليس 17، في المثال الأول. تعتمد أفضل قيمة للعناصر بدءًا من العنصر i فقط على i والمساحة المتبقية، وهي عدد صحيح يصل إلى 1000. تكفي خلية واحدة في الجدول لكل زوج، ما يعطي O(n × capacity)، ويكفي صف واحد إذا مررت على السعات تنازليًا.
جرّب كلا الخيارين لكل عنصر
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لتكن best(i, room) أكبر قيمة للعناصر من i فصاعدًا التي يمكن إضافتها مع وجود room وحدة فارغة؛ وبعد العنصر الأخير تكون القيمة 0. يؤدي تخطي العنصر i إلى best(i+1, room). أما وضعه في الحقيبة، عندما يكون weights[i] ≤ room، فيعطي values[i] + best(i+1, room-weights[i]). احتفظ بالقيمة الأكبر. كل طريقة تعبئة تلائم السعة هي تسلسل من اختيارات الوضع والتخطي، وتجرب الاستدعاءات العودية جميع هذه الاختيارات.
يتضاعف عدد المسارات مع كل عنصر. وعندما تلائم العناصر المئة كلها الحقيبة معًا، كما في حالة وزن كل عنصر 10 وسعة حقيبة 1000، يكون عدد المسارات 2^100.
الخوارزمية
- اكتب
best(i, room)؛ وأعِد 0 عندما يكونiبعد العنصر الأخير. - عيّن
skipإلىbest(i+1, room). - إذا كان
weights[i] > room، فأعِدskip. - وإلا فأعِد الأكبر من
skipوvalues[i] + best(i+1, room-weights[i]). - أعِد
best(0, capacity).
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)املأ جدولًا حسب العنصر والسعة
الفكرة
يصل الاستدعاء الذاتي إلى الزوج نفسه (i, room) عبر مسارات عديدة. يوجد على الأكثر 101 × 1001 زوجًا، أي نحو 10^5، لذا احسب كلًّا منها مرة واحدة.
لتكن best[i][c] أكبر قيمة يمكن أن تضعها العناصر i الأولى في حقيبة سعتها c؛ ويكون الصف 0 كله 0. بالنسبة إلى العنصر i-1 ذي الوزن w والقيمة v، فإن تركه يعطي best[i-1][c]، ووضعه في الحقيبة، عندما يكون w ≤ c، يعطي best[i-1][c-w] + v. لا يقرأ الصف i إلا الصف i-1، لذا يدخل كل عنصر في الخلية مرة واحدة على الأكثر.
في المثال الأول، يرفع العنصر 2 (وزنه 3 وقيمته 7) سعة 7 إلى best[2][4] + 7 = 17. ثم لا يقدّم العنصر 3 سوى best[3][2] + 12 = 16، لذا تظل الإجابة 17.
الخوارزمية
- أنشئ جدولًا يتكوّن من n+1 صفوف وcapacity+1 أعمدة، وجميع القيم فيه 0.
- لكل صف
iمن 1 إلى n، خذw = weights[i-1]وv = values[i-1]. - لكل سعة
c، عيّنbest[i][c]إلىbest[i-1][c]. - إذا كان
w ≤ cوكانتbest[i-1][c-w] + vأكبر، فخزّن هذه القيمة بدلًا منها. - أعِد
best[n][capacity].
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]صف واحد، والسعات تتناقص
الفكرة
يحتاج الصف i إلى الصف i-1 فقط، لذا احتفظ بصف واحد best[c] واكتب فوقه عنصرًا تلو الآخر. يحدد اتجاه المرور ما إذا كانت الإجابة صحيحة.
عند المرور تصاعديًا على c، قد تكون best[c-w] قد تضمنت العنصر الحالي بالفعل. إذا كان لدينا عنصر واحد وزنه 3 وقيمته 5 وسعة مقدارها 6، فستصبح قيمة السعة 3 هي 5، ثم تقرأ السعة 6 هذه القيمة وتصبح 10: أي نسختين. أما عند المرور تنازليًا من capacity إلى w، فالخلية التي تقرؤها تقع أسفل الخلية التي تكتب فيها، وسيتم الكتابة فوقها لاحقًا، لذا تظل محتفظة بقيمة الصف السابق.
يكون المرور التصاعدي هو الحلقة الصحيحة عندما تكون العناصر متاحة بنسخ غير محدودة. هنا يظل الزمن O(n × capacity)، بينما تنخفض الذاكرة إلى صف واحد.
الخوارزمية
- أنشئ
bestمعcapacity + 1من العناصر، وكلها 0. - لكل عنصر له وزن
wوقيمةv، مرّرcمنcapacityتنازليًا حتىw. - إذا كانت
best[c-w] + vأكبر منbest[c]، فخزّنها فيbest[c]. - أعِد
best[capacity].
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
أخطاء شائعة وحالات حدّية
- يؤدي المرور على السعات تصاعديًا في نسخة الصف الواحد إلى احتساب العنصر مرتين: فعنصر وزنه 3 وقيمته 5 في حقيبة سعتها 6 يعطي نتيجة 10 بدلًا من 5.
- استخدام صف من
capacityمدخلات بدلًا منcapacity + 1. عندئذٍ، تؤدي إعادةbest[capacity-1]إلى فقدان أي تعبئة تملأ الحقيبة تمامًا، مثل عنصر وزنه 1 في حقيبة سعتها 1. - بدء المدخلات من سالب ما لا نهاية. ليس من الضروري أن تكون الحقيبة ممتلئة، لذا تبدأ كل المدخلات من 0؛ أما مع سالب ما لا نهاية، فيُعيد المثال الثالث سالب ما لا نهاية بدلًا من 0.
- يجب تخطي أي عنصر أثقل من سعة الحقيبة. في المثال الثالث، يوقف النطاق المغلق
w...capacityالبرنامج في Swift، بينما يعدّ(w+1):(capacity+1)تنازليًا في R.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة حقيبة الظهر 0/1؟
يعمل الجدول في زمن O(n × capacity)، أي نحو 10^5 خطوة لـ 100 عنصر وسعة مقدارها 1000، وتستخدم النسخة ذات الصف الواحد ذاكرة O(capacity). الحدّ شبه متعدد الحدود: فهو ينمو مع قيمة السعة، لا مع عدد خاناتها. المسألة العامة صعبة من نوع NP.
لماذا لا تعمل الخوارزمية الجشعة مع مشكلة حقيبة الظهر 0/1؟
القاعدة الجشعة لا تتراجع أبدًا عن اختيار، حتى عندما يترك العنصر مساحة لا يملؤها شيء. بسعة 7، يتعادل العنصر ذو الوزن 5 والقيمة 10 في أفضل نسبة، ومع ذلك تبلغ قيمة العنصرين ذوي الوزنين 4 و3 معًا 13. تكون الخوارزمية الجشعة حسب النسبة مثالية فقط لحقيبة الظهر الكسرية، حيث يمكنك تقسيم العناصر.
كيف تعرف العناصر التي اختارتها مسألة حقيبة الظهر 0/1؟
احتفظ بالجدول كاملًا، وارجع منه بدءًا من best[n][capacity]. إذا كانت قيمة best[i][c] مختلفة عن best[i-1][c]، فهذا يعني أن العنصر i-1 قد أُدرج في الحقيبة، لذا سجّله واطرح وزنه من c. وإلا فانتقل إلى الصف i-1 مع الإبقاء على c كما هو.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def knapsack(weights, values, capacity):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
الإخراج المتوقع
17