dynamic-programming
Problem ze zmianą monet
Szukaj…
Liczba sposobów na uzyskanie sumy
Biorąc pod uwagę monety o różnych nominałach i sumę, na ile sposobów możemy połączyć te monety, aby uzyskać sumę? Powiedzmy, że mamy coins = {1, 2, 3}
a w total = 5
, możemy uzyskać sumę na 5 sposobów:
- 1 1 1 1 1
- 1 1 1 2
- 1 1 3
- 1 2 2
- 2 3
Problem jest ściśle związany z problemem plecaka. Jedyną różnicą jest to, że mamy nieograniczoną podaż monet. Użyjemy programowania dynamicznego, aby rozwiązać ten problem.
Użyjemy tablicy 2D dp [n] [razem + 1], gdzie n jest liczbą różnych nominałów monet, które mamy. W naszym przykładzie potrzebujemy dp [3] [6] . Tutaj dp [i] [j] będzie oznaczać liczbę sposobów, w jakie możemy uzyskać j , gdybyśmy mieli monety od monet [0] do monet [i] . Na przykład dp [1] [2] zapisze, jeśli mamy monety [0] i monety [1] , na ile sposobów możemy zrobić 2 . Zaczynajmy:
W przypadku dp [0] [0] zadajemy sobie pytanie, czy mieliśmy tylko 1 nominał monety, czyli monety [0] = 1 , na ile sposobów możemy uzyskać 0 ? Odpowiedź jest 1 sposób, który jest, jeśli nie podejmiemy żadnej monety w ogóle. Idąc dalej, dp [0] [1] będzie reprezentować, gdybyśmy mieli tylko monety [0] , na ile sposobów możemy uzyskać 1 ? Odpowiedź brzmi ponownie 1 . W ten sam sposób dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] będzie wynosić 1 . Nasza tablica będzie wyglądać następująco:
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | | | | | | |
+---+---+---+---+---+---+---+
(3) | 2 | | | | | | |
+---+---+---+---+---+---+---+
W przypadku dp [1] [0] zadajemy sobie pytanie, czy mieliśmy monety 2 nominałów, to znaczy, czy mieliśmy monety [0] = 1 i monety [1] = 2 , na ile sposobów możemy zrobić 0 ? Odpowiedź to 1 , czyli brak przyjmowania monet. W przypadku dp [1] [1] , ponieważ monety [1] = 2 są większe niż nasza obecna suma, 2 nie przyczyni się do uzyskania sumy. Wykluczymy więc 2 i policzymy liczbę sposobów uzyskania sumy za pomocą monet [0] . Ale ta wartość jest już zapisana w dp [0] [1] ! Więc weźmiemy wartość z góry. Nasza pierwsza formuła:
if coins[i] > j
dp[i][j] := dp[i-1][j]
end if
W przypadku dp [1] [2] , na ile sposobów możemy uzyskać 2 , gdybyśmy mieli monety o nominałach 1 i 2 ? Możemy zrobić 2 używając monet o nominale 1 , które jest reprezentowane przez dp [0] [2] , ponownie możemy wziąć 1 nominał 2, który jest przechowywany w dp [1] [2-monety [i]] , gdzie i = 1 . Dlaczego? Będzie to oczywiste, jeśli spojrzymy na następny przykład. W przypadku dp [1] [3] , na ile sposobów możemy uzyskać 3 , gdybyśmy mieli monety o nominałach 1 i 2 ? Możemy wykonać 3 za pomocą monet o nominale 1 na 1 sposób, które są przechowywane w dp [0] [3] . Teraz, jeśli weźmiemy 1 nominał z 2 , będziemy potrzebować 3 - 2 = 1, aby uzyskać sumę. Liczba sposobów uzyskania 1 za pomocą monet o nominale 1 i 2 jest przechowywana w dp [1] [1] , który można zapisać jako dp [i] [j-monety [i]] , gdzie i = 1 . Dlatego zapisaliśmy poprzednią wartość w ten sposób. Nasza druga i ostatnia formuła będzie:
if coins[i] <= j
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
To dwie wymagane formuły do wypełnienia całej tablicy dp . Po wypełnieniu tablica będzie wyglądać następująco:
+---+---+---+---+---+---+---+
(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] będzie zawierać naszą wymaganą odpowiedź. Algorytm:
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]
Złożoność czasowa tego algorytmu wynosi O(n * total)
, gdzie n jest liczbą posiadanych przez nas nominałów monet.
Minimalna liczba monet, aby uzyskać sumę
Biorąc pod uwagę monety o różnych nominałach i sumę, ile monet musimy połączyć, aby uzyskać sumę, jeśli użyjemy minimalnej liczby monet? Powiedzmy, że mamy coins = {1, 5, 6, 8}
a w total = 11
, możemy uzyskać sumę za pomocą 2 monet, czyli {5, 6}
. Jest to rzeczywiście minimalna liczba monet wymaganych do zdobycia 11 . Zakładamy również, że istnieje nieograniczona podaż monet. Użyjemy programowania dynamicznego, aby rozwiązać ten problem.
Użyjemy tablicy 2D dp [n] [razem + 1], gdzie n jest liczbą różnych nominałów monet, które mamy. W naszym przykładzie potrzebujemy dp [4] [12] . W tym przypadku dp [i] [j] będzie oznaczać minimalną liczbę monet potrzebną do uzyskania j , gdybyśmy mieli monety od monet [0] do monet [i] . Na przykład dp [1] [2] zapisze, jeśli mieliśmy monety [0] i monety [1] , jaka jest minimalna liczba monet, których możemy użyć do zrobienia 2 . Zaczynajmy:
Początkowo dla 0 kolumny można uzyskać 0 , nie biorąc wcale monet. Zatem wszystkie wartości 0 kolumny będą wynosić 0 . W przypadku dp [0] [1] zadajemy sobie pytanie, czy mieliśmy tylko 1 nominał monety, czyli monety [0] = 1 , jaka jest minimalna liczba monet potrzebna do uzyskania 1 ? Odpowiedź to 1 . W przypadku dp [0] [2] , gdybyśmy mieli tylko 1 , jaka jest minimalna liczba monet potrzebnych do uzyskania 2 . Odpowiedź to 2 . Podobnie dp [0] [3] = 3 , dp [0] [4] = 4 i tak dalej. Należy tu wspomnieć, że jeśli nie mielibyśmy monety o nominale 1 , mogą istnieć przypadki, w których sumy nie można osiągnąć za pomocą tylko 1 monety. Dla uproszczenia bierzemy 1 w naszym przykładzie. Po pierwszej iteracji nasza tablica dp będzie wyglądać następująco:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Idąc dalej, w przypadku DP [1] [1] zadajemy sobie pytanie, czy mieliśmy monety [0] = 1 i monety [1] = 5 , jaka jest minimalna liczba monet potrzebnych do uzyskania 1 ? Ponieważ monety [1] są większe niż nasza obecna suma, nie wpłynie to na nasze obliczenia. Musimy wykluczyć monety [5] i zdobyć 1 za pomocą monet [0] tylko. Ta wartość jest przechowywana w dp [0] [1] . Tak więc bierzemy wartość z góry. Nasza pierwsza formuła to:
if coins[i] > j
dp[i][j] := dp[i-1][j]
Ten warunek będzie spełniony, dopóki nasza suma nie będzie wynosić 5 w dp [1] [5] , w takim przypadku możemy wykonać 5 na dwa sposoby:
- Bierzemy 5 nominałów monet [0] , które są przechowywane na dp [0] [5] (od góry).
- Przyjmujemy 1 nominał monet [1] i ( 5 - 5 ) = 0 nominałów monet [0] .
Wybierzemy minimum tych dwóch. Więc dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Dlaczego wspomnieliśmy o 0 nominałach monet [0] tutaj będzie widoczne na naszej następnej pozycji.
Dla dp [1] [6] możemy zrobić 6 na dwa sposoby:
- Bierzemy 6 nominałów monet [0] , które są przechowywane na górze.
- Możemy wziąć 1 nominał 5 , potrzebujemy 6 - 5 = 1, aby uzyskać sumę. Minimalna liczba sposobów uzyskania 1 za pomocą monet o nominale 1 i 5 jest przechowywana w dp [1] [1] , który można zapisać jako dp [i] [j-monety [i]] , gdzie i = 1 . Właśnie dlatego tak zapisaliśmy poprzednią wartość.
Przyjmiemy minimum tych dwóch sposobów. Zatem naszą drugą formułą będzie:
if coins[i] >= j
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
Za pomocą tych dwóch formuł możemy wypełnić cały stół. Nasz końcowy wynik to:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nasz wymagany wynik zostanie zapisany w dp [3] [11] . Procedura będzie:
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]
Złożoność tego algorytmu w środowisku wykonawczym wynosi: O (n * ogółem), gdzie n jest liczbą nominałów monet.
Aby wydrukować potrzebne monety, musimy sprawdzić:
- jeśli wartość pochodzi z góry, bieżąca moneta nie jest uwzględniana.
- jeśli wartość pochodzi od lewej, obecna moneta jest uwzględniana.
Algorytm wyglądałby następująco:
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
W naszym przykładzie kierunek będzie następujący:
Wartości będą wynosić 6 , 5 .