Onbegrensde knapsack en coin-change-DP

In het onbeperkte knapzakprobleem kun je elk voorwerp zo vaak meenemen als je wilt. Denk aan munten in een automaat, niet aan een vaste stapel.

Vergeleken met 0/1 verandert alleen de richting van de lus. Bij onbeperkte voorwerpen doorloop je de capaciteit vooruit, van laag naar hoog.

Als je vooruitgaat, kan dp[w - coin] ditzelfde voorwerp al bevatten. Dat opzettelijke hergebruik maakt het precies mogelijk om het opnieuw mee te nemen.

Het klassieke muntwisselprobleem vraagt naar het kleinste aantal munten dat samen een bedrag vormt. Het is onbeperkte DP met een minimum in plaats van een maximum.

Laat dp[a] het kleinste aantal munten zijn dat nodig is om bedrag a te maken. Begin met dp[0] = 0, want voor nul zijn geen munten nodig.

Onbereikbare bedragen beginnen als oneindig. Als een bedrag aan het einde oneindig blijft, kan geen enkele combinatie van munten het vormen.

Probeer voor elke munt elk bedrag dat je ermee kunt bereiken te verbeteren. Gebruik één munt meer dan het kleinere overgebleven bedrag.

Door de bedragen oplopend te doorlopen, telt dp[a - coin] deze munt al mee. Zo kan één munt meerdere keren bijdragen.

Vervang min+1 door een som om het aantal manieren te tellen waarop je elk bedrag kunt maken. Met de muntlus buitenom voorkom je dat je volgordes dubbel telt.

Je antwoord staat in dp[amount]. In de minimumvariant betekent een oneindige waarde dat het doelbedrag niet kan worden gevormd.

Onthoud de ene omschakeling: een capaciteit die achteruit loopt betekent elk voorwerp één keer, vooruit betekent onbeperkt. Dezelfde tabel, tegengestelde doorlooprichting.

Je hebt de lus vooruit gedraaid voor onbeperkt hergebruik en muntwisselen opgebouwd met een minimum voor het kleinste aantal munten of een som voor het totale aantal manieren. 💰