حقيبة الظهر غير المحدودة وتغيير العملات II
اسمح بإعادة استخدام العناصر عبر تكرار السعة إلى الأمام، وحلّ مسألتي coin-change-II (عدّ الطرق) وتقطيع القضيب باستخدام هذا المتغير.
حقيبة الظهر غير المحدودة وتغيير العملات II درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
مفهوم حقيبة الظهر غير المحدودة
في حقيبة الظهر غير المحدودة، يمكن اختيار كل عنصر أي عدد من المرات (على خلاف حقيبة الظهر 0/1، حيث يُستخدم كل عنصر مرة واحدة على الأكثر). يظل تعريف الحالة نفسه — dp[c] = أكبر قيمة يمكن تحقيقها بسعة c — لكن يتغير اتجاه التكرار. وبما أن العناصر قابلة لإعادة الاستخدام، فعند تحديث dp[c] نريد السماح باستخدام العنصر الحالي مرة أخرى، ولذلك نكرّر السعة من اليسار إلى اليمين (تكرارًا تصاعديًا).
التكرار التصاعدي يتيح إعادة الاستخدام
تذكّروا أننا في حقيبة الظهر 0/1 كرّرنا من اليمين إلى اليسار لمنع إعادة الاستخدام. أما في حقيبة الظهر غير المحدودة فنفعل العكس: نكرّر من اليسار إلى اليمين. عند حساب dp[c]، تكون dp[c-w] قد حُدّثت بالفعل في المرور الحالي — ما يعني أن العنصر i ربما أُدرج من قبل. وهذا بالضبط ما نريده: يمكن إضافة العنصر i مرة أخرى إلى حل يتضمن العنصر i أصلًا.
def unbounded_knapsack(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): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9Coin Change II: عدّ الطرق
تطرح Coin Change II السؤال الآتي: عند إعطائكم فئات العملات ومبلغًا معينًا، كم عدد الطرق المختلفة لتكوين هذا المبلغ (مع إمكانية استخدام كل عملة عددًا غير محدود من المرات)؟ هذه نسخة من حقيبة الظهر غير المحدودة، لكن بدلًا من تعظيم القيمة، نقوم بـعدّ التركيبات. عرّفوا dp[c] على أنه عدد الطرق لتكوين المبلغ c. الحالة الأساسية: dp[0] = 1 (هناك طريقة واحدة لتكوين 0: عدم اختيار أي شيء).
تنفيذ Coin Change II
لكل عملة، كرّروا المبالغ من اليسار إلى اليمين واجمعوا القيم: dp[c] += dp[c - coin]. تهيّئ الحالة الأساسية dp[0] = 1 عملية العد. لاحظوا أن الحلقة الخارجية تمر على العملات، بينما تمر الحلقة الداخلية على المبالغ — وهذا يعطي طبيعيًا عدد التركيبات (وليس التبديلات)، لأن كل فئة عملات تؤخذ في الاعتبار مرة واحدة فقط ضمن المرور الخارجي.
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1التركيبات مقابل التبديلات
يؤثر ترتيب الحلقات تأثيرًا حاسمًا. إذا وضعنا المبلغ في الحلقة الخارجية والعملة في الحلقة الداخلية، فسنعدّ التبديلات (أي إن الترتيب مهم). بالنسبة إلى amount=5 والعملات [1,2]، سيُعدّ كل من 1+2+2 و2+1+2 على حدة. أما إذا وضعنا العملة في الحلقة الخارجية، فسنعدّ التركيبات (أي إن الترتيب لا يهم): يكون 1+2+2 و2+1+2 الشيء نفسه. تطلب Coin Change II حساب التركيبات، ولذلك تكون العملة في الحلقة الخارجية.
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13مشكلة تقطيع القضيب
هذه مشكلة كلاسيكية أخرى من حقيبة الظهر غير المحدودة: لديكم قضيب طوله n وأسعار لكل طول من أطوال القضيب من 1 إلى n، والمطلوب إيجاد أكبر إيراد عبر تقطيع القضيب بطريقة مثلى. يمكن بيع كل قطعة طولها l بسعر price[l]، كما يمكن إعادة استخدام القطع (إذ يمكن تقطيع القضيب إلى عدة قطع بالطول نفسه). يناظر هذا مباشرةً حقيبة الظهر غير المحدودة، حيث W = n والعناصر هي أطوال القطع المختلفة.
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22Coin Change I: الحد الأدنى من العملات
تطرح Coin Change I (وهي مشكلة مختلفة) السؤال عن الحد الأدنى لعدد العملات اللازمة لتكوين مبلغ مستهدف. هنا dp[c] = الحد الأدنى لعدد العملات اللازمة لتكوين المبلغ c. علاقة التكرار: dp[c] = min(dp[c], dp[c - coin] + 1). هيّئوا جميع الإدخالات بالقيمة inf باستثناء dp[0] = 0. هذه أيضًا مشكلة غير محدودة (إذ يمكن إعادة استخدام العملات)، ولذلك يجب التكرار من اليسار إلى اليمين. أعيدوا dp[amount] إذا كانت قيمته منتهية، وإلا فأعيدوا -1.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1الفرق الأساسي: التعظيم مقابل التصغير مقابل العدّ
تستخدم الأنواع الثلاثة من حقيبة الظهر غير المحدودة عمليات مختلفة على dp[c-coin]: تعظيم القيمة: dp[c] = max(dp[c], dp[c-w] + v)؛ وتُهيّأ بالقيمة 0. تصغير التكلفة: dp[c] = min(dp[c], dp[c-coin] + 1)؛ وتُهيّأ بالقيمة inf، مع dp[0]=0. عدّ الطرق: dp[c] += dp[c-coin]؛ وتُهيّأ بالقيمة 0، مع dp[0]=1. إن تحديد النوع المناسب يمثل نصف الحل في مسائل المقابلات.
التعقيد ونصائح المقابلات
تعمل جميع أنواع حقيبة الظهر غير المحدودة بزمن O(n × W) ومساحة O(W)، حيث إن n هو عدد أنواع العناصر وW هو المبلغ المستهدف. في مسائل العملات، يكون n هو عدد فئات العملات. في المقابلات، حدّدوا النوع (تعظيم/تصغير/عدّ)، واكتبوا البرمجة الديناميكية أحادية البعد، ووضّحوا صراحةً ما إذا كانت الحلقة الخارجية تمر على العملات أم على المبلغ — فالمحاورون يعرفون أن هذا الفرق يختبر الفهم العميق للبرمجة الديناميكية.
تحديد الفرق بين حقيبة الظهر غير المحدودة وحقيبة الظهر 0/1
استخدموا المؤشرات التالية لتحديد النوع المناسب: إعادة الاستخدام غير المحدودة → حقيبة ظهر غير محدودة (تكرار تصاعدي)؛ استخدام كل عنصر مرة واحدة تمامًا → حقيبة ظهر 0/1 (تكرار تنازلي)؛ إذا ذكرت المسألة أي عدد من المرات، أو مخزونًا لا نهائيًا، أو السماح بإعادة الاستخدام → فهي حقيبة ظهر غير محدودة. أمثلة: مسائل العملات، وتقطيع القضيب، وInteger Break — كلها غير محدودة. أما مجموعات العناصر الفرعية والتقسيم وحقيبة الظهر 0/1 — فهي من نوع 0/1. يؤدي الخطأ في تحديد النوع إلى إجابات خاطئة يصعب تصحيحها.
Integer Break ومتغيرات أخرى
تطلب مسألة Integer Break (LeetCode 343) تقسيم عدد صحيح n إلى عددين صحيحين موجبين أو أكثر لتعظيم حاصل ضربهما. هذه مسألة حقيبة ظهر غير محدودة، حيث تكون العناصر هي الأعداد الصحيحة من 2 إلى n-1. عرّفوا dp[i] على أنه أكبر حاصل ضرب لأعداد مجموعها i. ولكل عنصر j من 2 إلى i، تكون dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). يوضّح هذا كيف يمكن تعميم نمط حقيبة الظهر غير المحدودة خارج سياق العملات.
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
ملخص الدرس
لقد تعلّمتم في هذا الدرس: تكرّر حقيبة الظهر غير المحدودة السعة من اليسار إلى اليمين للسماح بإعادة استخدام العناصر، وتعدّ Coin Change II التركيبات عبر وضع العملة في الحلقة الخارجية، وتختلف الأنواع الثلاثة — التعظيم والتصغير والعدّ — فقط في عملية البرمجة الديناميكية وتهيئتها. بعد ذلك نستخدم حقيبة الظهر 0/1 لحل مسألة Partition Equal Subset Sum.
الأسئلة الشائعة
هل درس «حقيبة الظهر غير المحدودة وتغيير العملات II» مجاني؟
نعم — نص درس «حقيبة الظهر غير المحدودة وتغيير العملات II» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «حقيبة الظهر غير المحدودة وتغيير العملات II»؟
اسمح بإعادة استخدام العناصر عبر تكرار السعة إلى الأمام، وحلّ مسألتي coin-change-II (عدّ الطرق) وتقطيع القضيب باستخدام هذا المتغير. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «حقيبة الظهر غير المحدودة وتغيير العملات II»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة الظهر 0/1 وتحسين المساحة
- حقيبة الظهر غير المحدودة وتغيير العملات II
- مجموع مجموعة جزئية متساوية للتقسيم
- المجموع المستهدف بإشارات موجبة وسالبة