dynamic-programming
Coin Changing Problem
Ricerca…
Numero di modi per ottenere totale
Dato le monete di diverse denominazioni e un totale, in quanti modi possiamo combinare queste monete per ottenere il totale? Diciamo che abbiamo coins = {1, 2, 3}
e un total = 5
, possiamo ottenere il totale in 5 modi:
- 1 1 1 1 1
- 1 1 1 2
- 1 1 3
- 1 2 2
- 2 3
Il problema è strettamente correlato al problema dello zaino. L'unica differenza è che abbiamo una scorta illimitata di monete. Useremo la programmazione dinamica per risolvere questo problema.
Useremo un array 2D dp [n] [totale + 1] dove n è il numero di diverse denominazioni di monete che abbiamo. Per il nostro esempio, avremo bisogno di dp [3] [6] . Qui dp [i] [j] indicherà il numero di modi in cui possiamo ottenere j se avessimo monete da monete [0] fino a monete [i] . Ad esempio dp [1] [2] memorizzerà se avessimo monete [0] e monete [1] , in quanti modi potremmo fare 2 . Cominciamo:
Per dp [0] [0] , ci stiamo chiedendo se avessimo solo 1 denominazione di moneta, cioè monete [0] = 1 , in quanti modi possiamo ottenere 0 ? La risposta è 1 way, ovvero se non prendiamo nessuna moneta. Andando avanti, dp [0] [1] rappresenterà se avessimo solo monete [0] , in quanti modi possiamo ottenere 1 ? La risposta è di nuovo 1 . Allo stesso modo, dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] sarà 1 . Il nostro array sarà simile a:
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | | | | | | |
+---+---+---+---+---+---+---+
(3) | 2 | | | | | | |
+---+---+---+---+---+---+---+
Per dp [1] [0] , ci stiamo chiedendo se avessimo monete di 2 denominazioni, cioè se avessimo monete [0] = 1 e monete [1] = 2 , in quanti modi potremmo fare 0 ? La risposta è 1 , che è senza prendere monete. Per dp [1] [1] , poiché coins [1] = 2 è maggiore del nostro totale attuale, 2 non contribuirà a ottenere il totale. Quindi escluderemo 2 e conteremo il numero di modi in cui possiamo ottenere il totale utilizzando le monete [0] . Ma questo valore è già memorizzato in dp [0] [1] ! Quindi prenderemo il valore dall'alto. La nostra prima formula:
if coins[i] > j
dp[i][j] := dp[i-1][j]
end if
Per dp [1] [2] , in quanti modi possiamo ottenere 2 , se avessimo monete di denominazione 1 e 2 ? Possiamo fare 2 usando monete di denominazione di 1 , che è rappresentata da dp [0] [2] , di nuovo possiamo prendere 1 denominazione di 2 che è memorizzata in dp [1] [2-coins [i]] , dove io = 1 . Perché? Sarà chiaro se guardiamo al prossimo esempio. Per dp [1] [3] , in quanti modi possiamo ottenere 3 , se avessimo monete di denominazione 1 e 2 ? Possiamo fare 3 usando monete di denominazione 1 in 1 modo, che è memorizzato in dp [0] [3] . Ora se prendiamo 1 denominazione di 2 , avremo bisogno di 3 - 2 = 1 per ottenere il totale. Il numero di modi per ottenere 1 usando le monete di denominazione 1 e 2 è memorizzato in dp [1] [1] , che può essere scritto come, dp [i] [j-coins [i]] , dove i = 1 . Questo è il motivo per cui abbiamo scritto il valore precedente in questo modo. La nostra seconda e ultima formula sarà:
if coins[i] <= j
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
Queste sono le due formule richieste per riempire l'intero array dp . Dopo aver riempito la matrice apparirà come:
+---+---+---+---+---+---+---+
(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] conterrà la nostra risposta richiesta. L'algoritmo:
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]
La complessità temporale di questo algoritmo è O(n * total)
, dove n è il numero di tagli delle monete che abbiamo.
Numero minimo di monete da ottenere
Dato le monete di diverse denominazioni e un totale, quante monete dobbiamo combinare per ottenere il totale se usiamo il numero minimo di monete? Diciamo che abbiamo coins = {1, 5, 6, 8}
e un total = 11
, possiamo ottenere il totale utilizzando 2 monete che è {5, 6}
. Questo è davvero il numero minimo di monete necessarie per ottenere 11 . Assumeremo anche che ci siano quantità illimitate di monete. Useremo la programmazione dinamica per risolvere questo problema.
Useremo un array 2D dp [n] [totale + 1] dove n è il numero di diverse denominazioni di monete che abbiamo. Per il nostro esempio, avremo bisogno di dp [4] [12] . Qui dp [i] [j] indicherà il numero minimo di monete necessarie per ottenere j se avessimo monete da monete [0] fino a monete [i] . Ad esempio dp [1] [2] memorizzerà se avessimo monete [0] e monete [1] , qual è il numero minimo di monete che possiamo usare per fare 2 . Cominciamo:
All'inizio, per la 0 ° colonna, puoi fare 0 non prendendo alcuna moneta. Quindi, tutti i valori di 0 ° colonna sarà 0. Per dp [0] [1] , ci stiamo chiedendo se avessimo solo 1 denominazione di moneta, cioè monete [0] = 1 , qual è il numero minimo di monete necessarie per ottenere 1 ? La risposta è 1 . Per dp [0] [2] , se avessimo solo 1 , qual è il numero minimo di monete necessarie per ottenere 2 . La risposta è 2 . Allo stesso modo dp [0] [3] = 3 , dp [0] [4] = 4 e così via. Una cosa da ricordare qui è che, se non avessimo una moneta di denominazione 1 , potrebbero esserci alcuni casi in cui il totale non può essere raggiunto usando solo 1 moneta. Per semplicità prendiamo 1 nel nostro esempio. Dopo la prima iterazione, il nostro array dp sarà simile a:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Andando avanti, per dp [1] [1] , ci stiamo chiedendo se avessimo monete [0] = 1 e monete [1] = 5 , qual è il numero minimo di monete necessarie per ottenere 1 ? Poiché le monete [1] sono superiori al nostro totale attuale, non influenzeranno il nostro calcolo. Dovremo escludere monete [5] e ottenere 1 utilizzando solo monete [0] . Questo valore è memorizzato in dp [0] [1] . Quindi prendiamo il valore dall'alto. La nostra prima formula è:
if coins[i] > j
dp[i][j] := dp[i-1][j]
Questa condizione sarà vera finché il nostro totale sarà 5 in dp [1] [5] , in tal caso, possiamo fare 5 in due modi:
- Prendiamo 5 tagli di monete [0] , che sono memorizzati su dp [0] [5] (dall'alto).
- Prendiamo 1 denominazione di monete [1] e ( 5 - 5 ) = 0 denominazioni di monete [0] .
Scegliamo il minimo di questi due. Quindi dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Perché abbiamo menzionato 0 denominazioni di monete [0] qui saranno evidenti nella nostra prossima posizione.
Per dp [1] [6] , possiamo fare 6 in due modi:
- Prendiamo 6 denominazioni di monete [0] , che è memorizzato in alto.
- Possiamo prendere 1 denominazione di 5 , avremo bisogno di 6 - 5 = 1 per ottenere il totale. Il numero minimo di modi per ottenere 1 usando le monete di denominazione 1 e 5 è memorizzato in dp [1] [1] , che può essere scritto come dp [i] [j-coins [i]] , dove i = 1 . Questo è il motivo per cui abbiamo scritto il valore precedente in quel modo.
Prenderemo il minimo di questi due modi. Quindi la nostra seconda formula sarà:
if coins[i] >= j
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
Usando queste due formule possiamo riempire l'intera tabella. Il nostro risultato finale sarà:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Il risultato richiesto verrà archiviato in dp [3] [11] . La procedura sarà:
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]
La complessità di runtime di questo algoritmo è: O (n * totale) dove n è il numero di tagli di monete.
Per stampare le monete necessarie, dobbiamo controllare:
- se il valore proviene dall'alto, la moneta attuale non è inclusa.
- se il valore proviene da sinistra, allora la moneta attuale è inclusa.
L'algoritmo sarebbe:
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
Per il nostro esempio, la direzione sarà:
I valori saranno 6 , 5 .