برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات
استخدام العناصر أي عدد من المرات
برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
عناصر بلا حدود
في unbounded knapsack، يمكنك أخذ كل عنصر أي عدد من المرات. فكّر في العملات داخل آلة بيع، لا في كومة ثابتة من العناصر.
تغيير صغير واحد
بالمقارنة مع 0/1، لا يتغير إلا اتجاه الحلقة. ففي العناصر غير المحدودة، تكرّر على السعة منخفضة إلى مرتفعة.
إعادة الاستخدام إلى الأمام هي الفكرة
عند المرور إلى الأمام، قد تتضمن dp[w - coin] العنصر نفسه مسبقًا. وإعادة الاستخدام المقصودة هذه هي ما يتيح لك أخذه مرة أخرى.
تعرّف إلى مسألة تغيير العملات
تطلب مسألة coin change الكلاسيكية إيجاد أقل عدد من العملات التي يساوي مجموعها مبلغًا معينًا. إنها DP غير محدودة تستخدم القيمة الصغرى بدلًا من العظمى.
عرّف الحالة
لتكن dp[a] أقل عدد من العملات اللازمة لتكوين المبلغ a. ابدأ بتعيين dp[0] = 0، لأن تكوين الصفر لا يحتاج إلى عملات.
dp = [float("inf")] * (amount + 1)
dp[0] = 0استخدم اللانهاية للمبالغ المستحيلة
تبدأ المبالغ التي يتعذر الوصول إليها بقيمة اللانهاية. وإذا بقي مبلغ ما لا نهائيًا في النهاية، فلا يمكن تكوينه بأي توليفة من العملات.
الانتقال
لكل عملة، حاول تحسين كل مبلغ يمكنها الوصول إليه. استخدم عددًا يزيد بعملة واحدة عن المبلغ الأصغر المتبقي.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)لماذا يكون الترتيب تصاعديًا
يسمح المرور على المبالغ تصاعديًا بأن تكون dp[a - coin] قد احتسبت هذه العملة مسبقًا. وهكذا يمكن لعملة واحدة أن تسهم عدة مرات.
احسب عدد الطرق بدلًا من ذلك
استبدل min+1 بمجموع لحساب عدد الطرق لتكوين كل مبلغ. وتمنع حلقة العملات الخارجية احتساب الترتيبات مرتين.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]اقرأ النتيجة
توجد إجابتك في dp[amount]. وفي نسخة القيمة الصغرى، تعني القيمة اللانهائية أن تكوين الهدف مستحيل.
0/1 مقابل غير المحدودة
تذكّر التبديل الوحيد: تعني السعة بالعكس استخدام كل عنصر مرة واحدة، بينما يعني المرور إلى الأمام استخدامه بلا حدود. الجدول نفسه، لكن باتجاهي مرور متعاكسين.
تحقق سريع
اختبر ما الذي يجعل مسألة حقيبة الظهر غير محدودة.
مراجعة
غيّرت اتجاه الحلقة إلى الأمام للسماح بإعادة الاستخدام بلا حدود، وبنيت مسألة تغيير العملات باستخدام القيمة الصغرى لأقل عدد من العملات أو المجموع لإجمالي الطرق. 💰
الأسئلة الشائعة
هل درس «برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات» مجاني؟
نعم — نص درس «برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات»؟
استخدام العناصر أي عدد من المرات تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة 0/1: خذ أو اترك
- حقيبة محسّنة من حيث المساحة
- برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات
- مجموع المجموعة والتقسيم