dynamic-programming
Moneda que cambia el problema
Buscar..
Número de formas de obtener el total
Dadas monedas de diferentes denominaciones y un total, ¿de cuántas maneras podemos combinar estas monedas para obtener el total? Digamos que tenemos coins = {1, 2, 3} y un total = 5 , podemos obtener el total de 5 maneras:
- 1 1 1 1 1
- 1 1 1 2
- 1 1 3
- 1 2 2
- 2 3
El problema está estrechamente relacionado con el problema de la mochila. La única diferencia es que tenemos un suministro ilimitado de monedas. Vamos a utilizar la programación dinámica para resolver este problema.
Usaremos una matriz 2D dp [n] [total + 1] donde n es el número de diferentes denominaciones de monedas que tenemos. Para nuestro ejemplo, necesitaremos dp [3] [6] . Aquí dp [i] [j] indicará el número de formas en que podemos obtener j si tuviéramos monedas de monedas [0] hasta monedas [i] . Por ejemplo, dp [1] [2] almacenará si tuviéramos monedas [0] y monedas [1] , de cuántas maneras podríamos hacer 2 . Vamos a empezar:
Para dp [0] [0] , nos preguntamos si solo tenemos 1 denominación de moneda, es decir monedas [0] = 1 , ¿de cuántas maneras podemos obtener 0 ? La respuesta es de 1 manera, que es si no tomamos ninguna moneda en absoluto. Continuando, dp [0] [1] representará si solo tuviéramos monedas [0] , ¿de cuántas maneras podemos obtener 1 ? La respuesta es de nuevo 1 . De la misma manera, dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] será 1 . Nuestra matriz se verá como:
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | | | | | | |
+---+---+---+---+---+---+---+
(3) | 2 | | | | | | |
+---+---+---+---+---+---+---+
Para dp [1] [0] , nos preguntamos si teníamos monedas de 2 denominaciones, es decir, si tuviéramos monedas [0] = 1 y monedas [1] = 2 , ¿de cuántas maneras podríamos hacer 0 ? La respuesta es 1 , que es no tomar ninguna moneda. Para dp [1] [1] , dado que las monedas [1] = 2 es mayor que nuestro total actual, 2 no contribuirá a obtener el total. Por lo tanto, excluiremos 2 y contaremos el número de formas en que podemos obtener el total usando monedas [0] . ¡Pero este valor ya está almacenado en dp [0] [1] ! Así que vamos a tomar el valor de la parte superior. Nuestra primera fórmula:
if coins[i] > j
dp[i][j] := dp[i-1][j]
end if
Para dp [1] [2] , ¿de cuántas maneras podemos obtener 2 , si tuviéramos monedas de denominación 1 y 2 ? Podemos hacer 2 usando monedas de denominación de 1 , que están representadas por dp [0] [2] , otra vez podemos tomar 1 denominación de 2 que está almacenada en dp [1] [2-coins [i]] , donde i = 1 . ¿Por qué? Será evidente si nos fijamos en el siguiente ejemplo. Para dp [1] [3] , ¿de cuántas maneras podemos obtener 3 , si tuviéramos monedas de denominación 1 y 2 ? Podemos hacer 3 usando monedas de denominación 1 en 1 forma, que se almacenan en dp [0] [3] . Ahora, si tomamos 1 denominación de 2 , necesitaremos 3 - 2 = 1 para obtener el total. El número de formas de obtener 1 usando las monedas de denominación 1 y 2 se almacena en dp [1] [1] , que se puede escribir como, dp [i] [j-coins [i]] , donde i = 1 . Por eso escribimos el valor anterior de esta manera. Nuestra segunda y última fórmula será:
if coins[i] <= j
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
Estas son las dos fórmulas necesarias para completar toda la matriz dp . Después de llenar la matriz se verá como:
+---+---+---+---+---+---+---+
(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] contendrá nuestra respuesta requerida. El 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 complejidad temporal de este algoritmo es O(n * total) , donde n es el número de denominaciones de monedas que tenemos.
Cantidad mínima de monedas para obtener el total
Dadas las monedas de diferentes denominaciones y un total, ¿cuántas monedas necesitamos combinar para obtener el total si utilizamos el número mínimo de monedas? Digamos que tenemos coins = {1, 5, 6, 8} y un total = 11 , podemos obtener el total usando 2 monedas que es {5, 6} . Este es de hecho el número mínimo de monedas requeridas para obtener 11 . También asumiremos que hay un suministro ilimitado de monedas. Vamos a utilizar la programación dinámica para resolver este problema.
Usaremos una matriz 2D dp [n] [total + 1] donde n es el número de diferentes denominaciones de monedas que tenemos. Para nuestro ejemplo, necesitaremos dp [4] [12] . Aquí dp [i] [j] indicará el número mínimo de monedas necesarias para obtener j si tuviéramos monedas de monedas [0] hasta monedas [i] . Por ejemplo, dp [1] [2] almacenará si tuviéramos monedas [0] y monedas [1] , ¿cuál es el número mínimo de monedas que podemos usar para hacer 2 ? Vamos a empezar:
Al principio, para la columna 0 , puede hacer 0 al no tomar ninguna moneda. Así que todos los valores de 0 º columna será 0. Para dp [0] [1] , nos preguntamos si solo tenemos 1 denominación de moneda, es decir, monedas [0] = 1 , ¿cuál es el número mínimo de monedas necesarias para obtener 1 ? La respuesta es 1 . Para dp [0] [2] , si solo tuviéramos 1 , ¿cuál es el número mínimo de monedas necesarias para obtener 2 ? La respuesta es 2 . De manera similar, dp [0] [3] = 3 , dp [0] [4] = 4 y así sucesivamente. Una cosa a mencionar aquí es que, si no tenemos una moneda de denominación 1, puede haber algunos casos en los que no se puede lograr la total usando solamente 1 moneda. Por simplicidad tomamos 1 en nuestro ejemplo. Después de la primera iteración nuestra matriz dp se verá así:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Continuando, para dp [1] [1] , nos preguntamos si teníamos monedas [0] = 1 y monedas [1] = 5 , ¿cuál es el número mínimo de monedas necesarias para obtener 1 ? Como las monedas [1] son mayores que nuestro total actual, no afectará nuestro cálculo. Tendremos que excluir monedas [5] y obtener 1 usando monedas [0] solamente. Este valor se almacena en dp [0] [1] . Así que tomamos el valor de la parte superior. Nuestra primera fórmula es:
if coins[i] > j
dp[i][j] := dp[i-1][j]
Esta condición será verdadera hasta que nuestro total sea 5 en dp [1] [5] , para ese caso, podemos hacer 5 de dos maneras:
- Tomamos 5 denominaciones de monedas [0] , que se almacenan en dp [0] [5] (desde la parte superior).
- Tomamos 1 denominación de monedas [1] y ( 5 - 5 ) = 0 denominaciones de monedas [0] .
Elegiremos el mínimo de estos dos. Entonces dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . ¿Por qué mencionamos 0 denominaciones de monedas? [0] aquí será evidente en nuestra próxima posición.
Para dp [1] [6] , podemos hacer 6 de dos maneras:
- Tomamos 6 denominaciones de monedas [0] , que se almacenan en la parte superior.
- Podemos tomar 1 denominación de 5 , necesitaremos 6 - 5 = 1 para obtener el total. El número mínimo de formas de obtener 1 utilizando las monedas de denominación 1 y 5 se almacena en dp [1] [1] , que se puede escribir como dp [i] [j-coins [i]] , donde i = 1 . Por eso escribimos el valor anterior de esa manera.
Tomaremos el mínimo de estas dos formas. Así que nuestra segunda fórmula será:
if coins[i] >= j
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
Usando estas dos fórmulas podemos completar toda la tabla. Nuestro resultado final será:
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(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 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nuestro resultado requerido se almacenará en dp [3] [11] . El procedimiento será:
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 complejidad del tiempo de ejecución de este algoritmo es: O (n * total) donde n es el número de denominaciones de monedas.
Para imprimir las monedas necesarias, tenemos que comprobar:
- Si el valor vino de arriba, entonces la moneda actual no está incluida.
- Si el valor vino de la izquierda, entonces se incluye la moneda actual.
El algoritmo sería:
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
Para nuestro ejemplo, la dirección será:
Los valores serán 6 , 5 .