برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات

في unbounded knapsack، يمكنك أخذ كل عنصر أي عدد من المرات. فكّر في العملات داخل آلة بيع، لا في كومة ثابتة من العناصر.

بالمقارنة مع 0/1، لا يتغير إلا اتجاه الحلقة. ففي العناصر غير المحدودة، تكرّر على السعة منخفضة إلى مرتفعة.

عند المرور إلى الأمام، قد تتضمن dp[w - coin] العنصر نفسه مسبقًا. وإعادة الاستخدام المقصودة هذه هي ما يتيح لك أخذه مرة أخرى.

تطلب مسألة coin change الكلاسيكية إيجاد أقل عدد من العملات التي يساوي مجموعها مبلغًا معينًا. إنها DP غير محدودة تستخدم القيمة الصغرى بدلًا من العظمى.

لتكن dp[a] أقل عدد من العملات اللازمة لتكوين المبلغ a. ابدأ بتعيين dp[0] = 0، لأن تكوين الصفر لا يحتاج إلى عملات.

تبدأ المبالغ التي يتعذر الوصول إليها بقيمة اللانهاية. وإذا بقي مبلغ ما لا نهائيًا في النهاية، فلا يمكن تكوينه بأي توليفة من العملات.

لكل عملة، حاول تحسين كل مبلغ يمكنها الوصول إليه. استخدم عددًا يزيد بعملة واحدة عن المبلغ الأصغر المتبقي.

يسمح المرور على المبالغ تصاعديًا بأن تكون dp[a - coin] قد احتسبت هذه العملة مسبقًا. وهكذا يمكن لعملة واحدة أن تسهم عدة مرات.

استبدل min+1 بمجموع لحساب عدد الطرق لتكوين كل مبلغ. وتمنع حلقة العملات الخارجية احتساب الترتيبات مرتين.

توجد إجابتك في dp[amount]. وفي نسخة القيمة الصغرى، تعني القيمة اللانهائية أن تكوين الهدف مستحيل.

تذكّر التبديل الوحيد: تعني السعة بالعكس استخدام كل عنصر مرة واحدة، بينما يعني المرور إلى الأمام استخدامه بلا حدود. الجدول نفسه، لكن باتجاهي مرور متعاكسين.

اختبر ما الذي يجعل مسألة حقيبة الظهر غير محدودة.

غيّرت اتجاه الحلقة إلى الأمام للسماح بإعادة الاستخدام بلا حدود، وبنيت مسألة تغيير العملات باستخدام القيمة الصغرى لأقل عدد من العملات أو المجموع لإجمالي الطرق. 💰