حقيبة الظهر 0/1 وتحسين المساحة
اشتق علاقة تكرار حقيبة الظهر 0/1، واملأ الجدول ثنائي الأبعاد، ثم اختزله إلى مصفوفة أحادية البعد عبر تكرار السعة بترتيب عكسي.
حقيبة الظهر 0/1 وتحسين المساحة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مشكلة حقيبة الظهر 0/1
مشكلة حقيبة الظهر 0/1: لديكم n عناصر، لكل منها وزن w[i] وقيمة v[i]، وحقيبة ظهر سعتها W. اختاروا العناصر لتعظيم القيمة الإجمالية من دون تجاوز السعة. يُختار كل عنصر مرة واحدة تمامًا (0 = تخطّيه، 1 = اختياره). تُعد هذه المشكلة النموذج الأساسي لعائلة كبيرة من مسائل البرمجة الديناميكية في المقابلات، بما في ذلك partition-equal-subset-sum وtarget-sum.
حالة البرمجة الديناميكية وعلاقة التكرار
عرّفوا dp[i][c] على أنه أكبر قيمة يمكن تحقيقها باستخدام أول i من العناصر بسعة c. يوجد خياران للعنصر i: تخطّيه (dp[i-1][c]) أو اختياره إذا كان w[i] <= c (dp[i-1][c-w[i]] + v[i]). وتكون علاقة التكرار: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) عندما يكون w[i] <= c، وإلا فإن dp[i][c] = dp[i-1][c]. الحالة الأساسية: dp[0][c] = 0 لكل قيم c.
تنفيذ جدول البرمجة الديناميكية ثنائي الأبعاد
يحتوي الجدول ثنائي الأبعاد على (n+1) x (W+1) إدخالًا، ويُملأ صفًا بعد صف لكل عنصر. بعد ملء جميع الصفوف، تحتوي dp[n][W] على أكبر قيمة. يعمل هذا الحل بزمن O(n × W) ومساحة O(n × W) — وهو تعقيد شبه متعدد الحدود يكون فعالًا عندما تكون W صغيرة.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+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(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10لماذا نكرّر السعة تنازليًا في البرمجة الديناميكية أحادية الأبعاد
الملاحظة الأساسية هي أن الصف i يعتمد فقط على الصف i-1. لذلك يمكننا استخدام مصفوفة أحادية الأبعاد واحدة وتحديثها في مكانها. لكن إذا كرّرنا السعة c من اليسار إلى اليمين (من الأصغر إلى الأكبر)، فقد يُحتسب العنصر i مرتين — إذ يمكننا استخدام القيمة المحدّثة لـ c-w[i] التي تتضمن العنصر i أصلًا. ويضمن التكرار من اليمين إلى اليسار (من الأكبر إلى الأصغر) استخدام كل عنصر مرة واحدة على الأكثر أثناء تحديث الصف.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowتنفيذ محسّن للمساحة باستخدام بُعد واحد
بالاحتفاظ بمصفوفة واحدة فقط والتكرار من السعة W نزولًا إلى w[i]، نحصل على النتيجة نفسها التي يقدّمها الجدول ثنائي الأبعاد باستخدام مساحة O(W). ويظل التعقيد الزمني O(n × W). من المهم جدًا حفظ هذا التحسين للمساحة — فالمحاورون يطلبون كثيرًا اختزال حقيبة الظهر ثنائية الأبعاد إلى بُعد واحد.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10إعادة بناء العناصر المختارة
لإيجاد العناصر التي جرى اختيارها، تحتاجون إلى الجدول ثنائي الأبعاد كاملًا. بعد ملئه، ابدؤوا من dp[n][W] وتتبعوا الخطوات إلى الخلف: إذا كان dp[i][c] != dp[i-1][c]، فهذا يعني أن العنصر i أُدرج — اطرحوا وزنه من c وانتقلوا إلى الصف i-1. تابعوا حتى i = 0. أما التحسين أحادي الأبعاد فيتخلّى عن إمكانية إعادة البناء هذه.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+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(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))مثال عملي: تعظيم القيمة الإجمالية
لنفترض أن لدينا العناصر: weights=[2,3,4,5]، وvalues=[3,4,5,6]، وW=8. الحل الأمثل هو اختيار العنصر ذي الوزن 3 (وقيمته 4) والعنصر ذي الوزن 5 (وقيمته 6) — الوزن الإجمالي 8 والقيمة 10. ويمكن أيضًا اختيار العنصرين ذوي الوزنين 2 و5 — فتكون القيمة الإجمالية 9، أو العنصرين ذوي الوزنين 2 و3 — فتكون القيمة 7. تجد البرمجة الديناميكية القيمة العظمى 10 بشكل صحيح. لاحظوا أن النهج الجشع (اختيار أعلى نسبة قيمة إلى وزن) سيختار أولًا العنصر ذي النسبة 1.5 (الوزن 2 والقيمة 3) — وهذا ليس أمثل دائمًا.
حقيبة الظهر الجزئية مقابل حقيبة الظهر 0/1
في حقيبة الظهر الجزئية، يمكنكم اختيار أجزاء من العناصر. ويمكن حلها بطريقة جشعة عبر الترتيب حسب نسبة القيمة إلى الوزن. أما في حقيبة الظهر 0/1، فالعناصر غير قابلة للتجزئة — لذلك يفشل النهج الجشع، وتلزم البرمجة الديناميكية. يستخدم المحاورون هذا الفرق لاختبار معرفتكم بمواضع تطبيق النهج الجشع. إذا سُئلتم عن النسخة الجزئية، فاذكروا مباشرةً النهج الجشع مع الترتيب؛ أما إذا كانت المسألة من نوع 0/1، فاستخدموا البرمجة الديناميكية.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))التعقيد الزمني شبه متعدد الحدود
مشكلة حقيبة الظهر 0/1 هي NP-complete، ومع ذلك نحلّها بزمن O(nW). يزول هذا التناقض لأن O(nW) هو تعقيد شبه متعدد الحدود: فالقيمة W وليست حجم الإدخال. ويحتاج التمثيل الثنائي لـ W إلى O(log W) بت، لذا فإن التعقيد الحقيقي هو O(n × 2^(log W))، وهو أُسّي بالنسبة إلى حجم الإدخال. عندما تكون W صغيرة (مثلًا 10⁴)، تكون البرمجة الديناميكية عملية؛ أما عندما يمكن أن تصل W إلى 10⁹، فنحتاج إلى أساليب مختلفة.
متابعة المحاور: السعة الكبيرة
إذا فرض المحاور أن تكون W كبيرة جدًا (مثلًا 10⁹) بينما تكون n صغيرة، فإن البرمجة الديناميكية المعتادة لا تعود مناسبة. تشمل البدائل: (1) تقنية meet-in-the-middle بزمن O(2^(n/2) × n)، (2) التقريب الجشع للنسخة الجزئية، أو (3) البحث مع التفرّع والتقييد. في معظم مسائل المقابلات التي تكون فيها W <= 10⁵، تكون البرمجة الديناميكية أحادية البعد مع التكرار التنازلي هي الإجابة المتوقعة.
تقنية meet-in-the-middle للسعة الكبيرة
عندما تكون W كبيرة جدًا لكن n صغيرة (مثلًا n=40)، تصبح البرمجة الديناميكية المعتادة بزمن O(nW) غير ممكنة، كما أن البحث الشامل في 2^n مجموعة فرعية بطيء جدًا. تقسم تقنية meet-in-the-middle العناصر إلى نصفين، وتعدّد جميع المجموعات الفرعية وعددها 2^(n/2) لكل نصف، ثم توفّق بينها بطريقة مثلى. رتّبوا أحد النصفين حسب الوزن، ثم استخدموا البحث الثنائي لكل مجموعة فرعية من النصف الآخر للعثور على أفضل توافق ضمن السعة. يعمل هذا الحل بزمن O(2^(n/2) × n)، وهو عملي عندما تصل n إلى 40.
اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
ملخص الدرس
لقد تعلّمتم في هذا الدرس: تستخدم برمجة حقيبة الظهر 0/1 الديناميكية الحالة dp[i][c] لتمثيل أكبر قيمة باستخدام i من العناصر وسعة c، وتختار علاقة التكرار بين تخطي كل عنصر أو اختياره، ويكرّر تحسين المساحة أحادي الأبعاد السعة من اليمين إلى اليسار لمنع احتساب العناصر مرتين. بعد ذلك ندرس حقيبة الظهر غير المحدودة، حيث يمكن إعادة استخدام العناصر، ونطبّقها على Coin Change II.
الأسئلة الشائعة
هل درس «حقيبة الظهر 0/1 وتحسين المساحة» مجاني؟
نعم — نص درس «حقيبة الظهر 0/1 وتحسين المساحة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «حقيبة الظهر 0/1 وتحسين المساحة»؟
اشتق علاقة تكرار حقيبة الظهر 0/1، واملأ الجدول ثنائي الأبعاد، ثم اختزله إلى مصفوفة أحادية البعد عبر تكرار السعة بترتيب عكسي. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «حقيبة الظهر 0/1 وتحسين المساحة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة الظهر 0/1 وتحسين المساحة
- حقيبة الظهر غير المحدودة وتغيير العملات II
- مجموع مجموعة جزئية متساوية للتقسيم
- المجموع المستهدف بإشارات موجبة وسالبة