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à:

Direction Array

I valori saranno 6 , 5 .



Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow