dynamic-programming
Myntbytesproblem
Sök…
Antal sätt att få totalt
Med tanke på mynt med olika valörer och totalt, på hur många sätt kan vi kombinera dessa mynt för att få summan? Låt oss säga att vi har coins = {1, 2, 3}
och total = 5
, vi kan få summan på fem sätt:
- 1 1 1 1 1
- 1 1 1 2
- 1 1 3
- 1 2 2
- 2 3
Problemet är nära relaterat till ryggsäckproblem. Den enda skillnaden är att vi har obegränsat utbud av mynt. Vi kommer att använda dynamisk programmering för att lösa detta problem.
Vi använder en 2D-array dp [n] [total + 1] där n är antalet olika valörer av mynt som vi har. För vårt exempel behöver vi dp [3] [6] . Här anger dp [i] [j] antalet sätt vi kan få j om vi hade mynt från mynt [0] upp till mynt [i] . Till exempel kommer dp [1] [2] att lagra om vi hade mynt [0] och mynt [1] , på hur många sätt vi kunde göra 2 . Låt oss börja:
För dp [0] [0], vi frågar oss om vi bara hade en myntvalör, som är mynt [0] = 1, hur många sätt kan vi få 0? Svaret är ett sätt, vilket är om vi inte tar några mynt alls. Att gå vidare, dp [0] [1] kommer att representera om vi bara hade mynt [0] , på hur många sätt kan vi få 1 ? Svaret är igen 1 . På samma sätt kommer dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] att vara 1 . Vår matris kommer att se ut:
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | | | | | | |
+---+---+---+---+---+---+---+
(3) | 2 | | | | | | |
+---+---+---+---+---+---+---+
För dp [1] [0] frågar vi oss om vi hade mynt med 2 valörer, det vill säga om vi hade mynt [0] = 1 och mynt [1] = 2 , på hur många sätt kan vi göra 0 ? Svaret är 1 , vilket är genom att inte ta några mynt alls. För dp [1] [1], eftersom mynt [1] = 2 är större än vår nuvarande totala, kommer två inte att bidra till att få den totala. Så vi utesluter två och räknar antalet sätt vi kan få totalt med mynt [0] . Men detta värde är redan lagrat i dp [0] [1] ! Så vi tar värdet uppifrån. Vår första formel:
if coins[i] > j
dp[i][j] := dp[i-1][j]
end if
För dp [1] [2] , på hur många sätt kan vi få 2 , om vi hade mynt av valör 1 och 2 ? Vi kan göra 2 med användning av mynt av valören 1, vilken representeras av dp [0] [2], återigen kan vi ta en valör av 2 som är lagrad i dp [1] [2-mynt [i]], där i = 1 . Varför? Det kommer att framgå om vi tittar på nästa exempel. För dp [1] [3] , på hur många sätt kan vi få 3 om vi hade mynt i valör 1 och 2 ? Kan vi göra 3 med användning av mynt av valören 1 i ett sätt, som är lagrad i dp [0] [3]. Om vi nu tar 1 valör av 2 , behöver vi 3 - 2 = 1 för att få summan. Antalet sätt att få 1 med mynt i valören 1 och 2 lagras i dp [1] [1] , som kan skrivas som, dp [i] [j-coins [i]] , där i = 1 . Det är därför vi skrev det tidigare värdet på detta sätt. Vår andra och sista formel är:
if coins[i] <= j
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
Detta är de två erforderliga formlerna för att fylla i hela dp- arrayen. Efter att fylla i arrayet kommer att se ut som:
+---+---+---+---+---+---+---+
(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] innehåller vårt önskade svar. Algoritmen:
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]
Tiden komplexitet för denna algoritm är O(n * total)
, där n är antalet valörer av mynt vi har.
Minsta antal mynt att få totalt
Med tanke på mynt med olika valörer och totalt, hur många mynt behöver vi kombinera för att få summan om vi använder minsta antal mynt? Låt oss säga att vi har coins = {1, 5, 6, 8}
och total = 11
, vi kan få summan med 2 mynt som är {5, 6}
. Detta är verkligen det minsta antalet mynt som krävs för att få 11 . Vi antar också att det finns obegränsat utbud av mynt. Vi kommer att använda dynamisk programmering för att lösa detta problem.
Vi använder en 2D-array dp [n] [total + 1] där n är antalet olika valörer av mynt som vi har. För vårt exempel behöver vi dp [4] [12] . Här anger dp [i] [j] det minsta antalet mynt som behövs för att få j om vi hade mynt från mynt [0] upp till mynt [i] . Till exempel kommer dp [1] [2] att lagra om vi hade mynt [0] och mynt [1] , vilket är det minsta antalet mynt vi kan använda för att göra 2 . Låt oss börja:
Först, för 0: e kolumnen, kan du göra 0 genom att inte ta några mynt alls. Så alla värden på 0: e kolumnen kommer att vara 0 . För dp [0] [1], vi frågar oss om vi bara hade en myntvalör, som är mynt [0] = 1, vad är det minsta antalet mynt som behövs för att få en? Svaret är 1 . För dp [0] [2] , om vi bara hade 1 , vad är det minsta antalet mynt som behövs för att få 2 . Svaret är 2 . På liknande sätt dp [0] [3] = 3 , dp [0] [4] = 4 och så vidare. En sak att nämna här är att om vi inte hade ett mynt av valören 1, kan det finnas några fall där den totala inte kan uppnås med hjälp av endast ett mynt. För enkelhetens skull tar vi 1 i vårt exempel. Efter första iterationen kommer vår dp- array att se ut:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
När vi fortsätter, för dp [1] [1] , frågar vi oss om vi hade mynt [0] = 1 och mynt [1] = 5 , vad är det minsta antalet mynt som behövs för att få 1 ? Eftersom mynt [1] är större än vårt nuvarande totalt påverkar det inte vår beräkning. Vi måste utesluta mynt [5] och bara få 1 med mynt [0] . Detta värde lagras i dp [0] [1] . Så vi tar värdet uppifrån. Vår första formel är:
if coins[i] > j
dp[i][j] := dp[i-1][j]
Detta villkor kommer att vara sant tills vårt total är 5 i dp [1] [5] , för det fallet kan vi göra 5 på två sätt:
- Vi tar 5 valörer av mynt [0] , som lagras på dp [0] [5] (uppifrån).
- Vi tar 1 valör av mynt [1] och ( 5 - 5 ) = 0 valörer av mynt [0] .
Vi väljer minst av dessa två. Så dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Varför nämnde vi 0 valörer av mynt [0] här kommer att framgå i vår nästa position.
För dp [1] [6] kan vi göra 6 på två sätt:
- Vi tar 6 valörer av mynt [0] , som lagras på toppen.
- Vi kan ta 1 valör av 5 , vi behöver 6 - 5 = 1 för att få summan. Det minsta antalet sätt att få 1 med mynt i valören 1 och 5 lagras i dp [1] [1] , som kan skrivas som dp [i] [j-coins [i]] , där i = 1 . Det är därför vi skrev det tidigare värdet på det sättet.
Vi tar minsta möjliga av dessa två sätt. Så vår andra formel kommer att vara:
if coins[i] >= j
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
Med hjälp av dessa två formler kan vi fylla i hela tabellen. Vårt slutliga resultat blir:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Vårt önskat resultat kommer att lagras vid dp [3] [11] . Förfarandet är:
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]
Runtidkomplexiteten för denna algoritm är: O (n * totalt) där n är antalet valörer av mynt.
För att skriva ut de mynt som behövs måste vi kontrollera:
- om värdet kom uppifrån, ingår inte det nuvarande myntet.
- om värdet kom från vänster, ingår det nuvarande myntet.
Algoritmen skulle vara:
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
För vårt exempel är riktningen:
Värdena är 6 , 5 .