dynamic-programming
Muntwisselprobleem

Aantal manieren om totaal te krijgen

Gegeven munten van verschillende coupures en een totaal, op hoeveel manieren kunnen we deze munten combineren om het totaal te krijgen? Laten we zeggen dat we coins = {1, 2, 3} en een total = 5 , we kunnen het totaal op 5 manieren krijgen:

• 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

Het probleem houdt nauw verband met knapzakprobleem. Het enige verschil is dat we een onbeperkte voorraad munten hebben. We gaan dynamisch programmeren gebruiken om dit probleem op te lossen.

We gebruiken een 2D-array dp [n] [totaal + 1] waarbij n het aantal verschillende coupures van munten is dat we hebben. Voor ons voorbeeld hebben we dp [3] [6] nodig . Hier geeft dp [i] [j] het aantal manieren aan waarop we j kunnen krijgen als we munten hadden van munten [0] tot munten [i] . Bijvoorbeeld dp [1] [2] zal opslaan als we munten [0] en -munten [1], op hoeveel manieren we konden maken 2 had. Laten we beginnen:

Voor dp [0] [0] vragen we ons af of we slechts 1 muntwaarde hadden, dat wil zeggen munten [0] = 1 , op hoeveel manieren kunnen we 0 krijgen? Het antwoord is 1 manier, dat is als we helemaal geen munten nemen. Verder gaat dp [0] [1] als we alleen munten [0] hadden , op hoeveel manieren kunnen we 1 krijgen? Het antwoord is opnieuw 1 . Op dezelfde manier zullen dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] 1 zijn . Onze reeks ziet eruit als:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Voor dp [1] [0] vragen we ons af of we munten van 2 coupures hadden, dat wil zeggen of we munten [0] = 1 en munten [1] = 2 hadden , op hoeveel manieren konden we 0 maken ? Het antwoord is 1 , dat is door helemaal geen munten te nemen. Voor dp [1] [1] , omdat munten [1] = 2 groter is dan ons huidige totaal, zal 2 niet bijdragen aan het verkrijgen van het totaal. Dus we sluiten 2 uit en tellen het aantal manieren waarop we het totaal kunnen krijgen met munten [0] . Maar deze waarde is al opgeslagen in dp [0] [1] ! Dus nemen we de waarde van boven. Onze eerste formule:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

Voor dp [1] [2] , op hoeveel manieren kunnen we 2 krijgen als we munten van denominatie 1 en 2 hadden ? We kunnen 2 maken met munten van denominatie van 1 , die wordt voorgesteld door dp [0] [2] , opnieuw kunnen we 1 denominatie van 2 nemen die is opgeslagen in dp [1] [2-munten [i]] , waarbij i = 1 . Waarom? Het zal duidelijk zijn als we naar het volgende voorbeeld kijken. Voor dp [1] [3] , op hoeveel manieren kunnen we 3 krijgen, als we munten van denominatie 1 en 2 hadden ? We kunnen 3 maken met munten van denominatie 1 op 1 manier, die wordt opgeslagen in dp [0] [3] . Als we nu 1 denominatie van 2 nemen , hebben we 3 - 2 = 1 nodig om het totaal te krijgen. Het aantal manieren om 1 te krijgen met de munten van denominatie 1 en 2 wordt opgeslagen in dp [1] [1] , dat kan worden geschreven als, dp [i] [j-munten [i]] , waarbij i = 1 . Daarom schreven we de vorige waarde op deze manier. Onze tweede en laatste formule zal zijn:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

Dit zijn de twee vereiste formules om de hele dp- array op te vullen. Na het vullen ziet de array eruit als:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] zal ons vereiste antwoord bevatten. Het algoritme:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

De tijdcomplexiteit van dit algoritme is O(n * total) , waarbij n het aantal coupures van munten is dat we hebben.

Minimaal aantal munten om totaal te krijgen

Gegeven munten van verschillende coupures en een totaal, hoeveel munten moeten we combineren om het totaal te krijgen als we een minimum aantal munten gebruiken? Stel dat we coins = {1, 5, 6, 8} en een total = 11 , we kunnen het totaal krijgen met 2 munten, dat is {5, 6} . Dit is inderdaad het minimum aantal munten dat nodig is om 11 te krijgen. We nemen ook aan dat er een onbeperkte voorraad munten is. We gaan dynamisch programmeren gebruiken om dit probleem op te lossen.

We gebruiken een 2D-array dp [n] [totaal + 1] waarbij n het aantal verschillende coupures van munten is dat we hebben. Voor ons voorbeeld hebben we dp [4] [12] nodig . Hier geeft dp [i] [j] het minimum aantal munten aan dat nodig is om j te krijgen als we munten hadden van munten [0] tot munten [i] . Bijvoorbeeld dp [1] [2] zal opslaan als we munten [0] en munten [1] hadden , wat is het minimum aantal munten dat we kunnen gebruiken om 2 te maken. Laten we beginnen:

In het begin kan voor de 0 de kolom 0 maken door helemaal geen munten te nemen. Dus alle waarden van de 0 de kolom zijn 0 . Voor dp [0] [1] vragen we ons af of we slechts 1 muntwaarde hadden, dat wil zeggen munten [0] = 1 , wat is het minimum aantal munten dat nodig is om 1 te krijgen? Het antwoord is 1 . Voor dp [0] [2] , als we er maar 1 hadden , wat is dan het minimum aantal munten dat nodig is om 2 te krijgen. Het antwoord is 2 . Evenzo dp [0] [3] = 3 , dp [0] [4] = 4 enzovoort. Een ding om hier te vermelden is dat, als we geen munt van denominatie 1 hadden , er enkele gevallen kunnen zijn waarin het totaal niet kan worden bereikt met slechts 1 munt. Voor de eenvoud nemen we 1 in ons voorbeeld. Na de eerste iteratie ziet onze dp- array eruit als:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Voor dp [1] [1] vragen we ons af of we munten [0] = 1 en munten [1] = 5 hadden , wat is het minimum aantal munten dat nodig is om 1 te krijgen? Aangezien munten [1] groter zijn dan ons huidige totaal, heeft dit geen invloed op onze berekening. We moeten munten [5] uitsluiten en er 1 krijgen met alleen munten [0] . Deze waarde wordt opgeslagen in dp [0] [1] . Dus nemen we de waarde van de top. Onze eerste formule is:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

Deze voorwaarde zal gelden totdat ons totaal 5 is in dp [1] [5] , voor dat geval kunnen we 5 op twee manieren maken:

• We nemen 5 coupures van munten [0] , die worden opgeslagen op dp [0] [5] (van boven).
• We nemen 1 denominatie van munten [1] en ( 5 - 5 ) = 0 coupures van munten [0] .

We kiezen het minimum van deze twee. Dus dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Waarom we hier 0 coupures van munten [0] hebben genoemd, zal duidelijk zijn in onze volgende positie.

Voor dp [1] [6] kunnen we 6 op twee manieren maken:

• We nemen 6 coupures van munten [0] , die bovenaan worden opgeslagen.
• We kunnen 1 coupure van 5 nemen , we hebben 6 - 5 = 1 nodig om het totaal te krijgen. Het minimum aantal manieren om 1 te krijgen met de munten van denominatie 1 en 5 wordt opgeslagen in dp [1] [1] , dat kan worden geschreven als dp [i] [j-munten [i]] , waarbij i = 1 . Daarom schreven we de vorige waarde op die manier.

We nemen het minimum van deze twee manieren. Dus onze tweede formule zal zijn:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

Met behulp van deze twee formules kunnen we de hele tabel invullen. Ons uiteindelijke resultaat zal zijn:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Ons vereiste resultaat wordt opgeslagen op dp [3] [11] . De procedure zal zijn:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

De runtime-complexiteit van dit algoritme is: O (n * totaal) waarbij n het aantal coupures van munten is.

Om de benodigde munten af te drukken, moeten we het volgende controleren:

• als de waarde van boven kwam, is de huidige munt niet inbegrepen.
• als de waarde van links kwam, wordt de huidige munt opgenomen.

Het algoritme zou zijn:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

In ons voorbeeld zal de richting zijn:

De waarden zijn 6 , 5 .