Muchos consideran que el Problema del Cambio de Moneda es esencial para comprender el paradigma de programación conocido como Programación Dinámica . Los dos a menudo siempre están emparejados porque el problema del cambio de moneda abarca los conceptos de programación dinámica. Para los que no saben de programación dinámica es según Wikipedia,
“tanto un método de optimización matemática como un método de programación de computadoras… se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples”.
En otras palabras, el problema dinámico es un método de programación que se utiliza para simplificar un problema en partes más pequeñas. Por ejemplo, si te preguntaran simplemente ¿cuánto es 3 * 89? quizás no sepas la respuesta de tu cabeza ya que probablemente sepas lo que es 2 * 2. Sin embargo, si supieras lo que es 3 * 88 (264), entonces ciertamente puedes deducir 3 * 89. Todo lo que tendrías que hacer es agregue 3 al múltiplo anterior y obtendrá la respuesta de 267. Por lo tanto, esa es una explicación muy simple de lo que es la programación dinámica y tal vez ahora pueda ver cómo se puede usar para resolver problemas de gran complejidad de tiempo de manera efectiva.
Teniendo en cuenta la definición anterior de programación dinámica, ahora podemos pasar al problema del cambio de monedas.. El siguiente es un ejemplo de una de las muchas variaciones del problema del cambio de moneda. Dada una lista de monedas, es decir , 1 centavo, 5 centavos y 10 centavos , ¿puedes determinar el número total de combinaciones de las monedas en la lista dada para formar el número N ?
Ejemplo 1 : Suponga que le dan las monedas de 1 centavo, 5 centavos y 10 centavos con N = 8 centavos, ¿cuál es el número total de combinaciones de las monedas que puede organizar para obtener 8 centavos?
Input: N=8
Coins : 1, 5, 10
Output: 2
Explanation:
1 way:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 cents.
2 way:
1 + 1 + 1 + 5 = 8 cents.
Todo lo que estás haciendo es determinar todas las formas en que puedes llegar a la denominación de 8 centavos. Ocho 1 centavos sumados es igual a 8 centavos. Tres 1 centavo más Uno 5 centavos sumados son 8 centavos. Entonces hay un total de 2 formas dada la lista de monedas 1, 5 y 10 para obtener 8 centavos.
Ejemplo 2 : Suponga que le dan las monedas de 1 centavo, 5 centavos y 10 centavos con N = 10 centavos, ¿cuál es el número total de combinaciones de las monedas que puede organizar para obtener 10 centavos?
Input : N=10
Coins : 1, 5, 10
Output : 4
Explanation:
1 way:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10 cents.
2 way:
1 + 1 + 1 + 1 + 1 + 5 = 10 cents.
3 way:
5 + 5 = 10 cents.
4 way:
10 cents = 10 cents.
Ahora que conocemos el enunciado del problema y cómo encontrar la solución para valores más pequeños, ¿cómo determinaríamos el número total de combinaciones de monedas que suman valores más grandes ? Escribimos un programa. ¿Cómo escribimos el programa para calcular todas las formas de obtener valores más grandes de N? simple usamos programación dinámica . Recuerde que la idea detrás de la programación dinámica es cortar cada parte del problema en partes más pequeñas. Similar al ejemplo en la parte superior de la página. Si no conocemos el valor de 4 * 36 pero conocemos el valor de 4 * 35 (140), podemos sumar 4 a ese valor y obtener nuestra respuesta de 4 * 36 que, por cierto, es 144.
Bien, entendemos lo que tenemos que hacer, pero ¿cómo va a determinar un programa de cuántas maneras la lista de monedas puede generar N? Bueno, veamos que este ejemplo.
N = 12 Index of Array: [0, 1, 2] Array of coins: [1, 5, 10]
Esta es una array de monedas, 1 centavo, 5 centavos y 10 centavos. La N es de 12 centavos. Por lo tanto, debemos idear un método que pueda usar esos valores de monedas y determinar la cantidad de formas en que podemos hacer 12 centavos.
Pensando dinámicamente, necesitamos descubrir cómo agregar a los datos anteriores. Entonces, lo que eso significa es que tenemos que agregar a las soluciones anteriores en lugar de volver a calcular sobre los mismos valores. Claramente, tenemos que iterar a través de toda la array de monedas. También necesitamos una forma de ver si una moneda es más grande que el valor N.
Una forma de hacer esto es tener una array que cuente hasta el valor N-ésimo .
Así que…
variedad de formas:
[0, 0, 0 ..... Nth value] in our case it would be up to 12.
La razón para tener una array hasta el valor N-ésimo es que podemos determinar el número de formas en que las monedas componen los valores en el índice de la array de formas . Hacemos esto porque si podemos determinar que una moneda es más grande que ese valor en el índice, entonces claramente no podemos usar esa moneda para determinar las combinaciones de las monedas porque esa moneda es más grande que ese valor. Esto se puede entender mejor con un ejemplo.
Usando los números anteriores como ejemplo.
N = 12 Index of Array of Coins: [0, 1, 2] Array of coins: [1, 5, 10] Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Antes de comenzar a iterar, debemos dar un valor predefinido a nuestra array de formas. Debemos establecer el primer elemento en el índice 0 de la array de formas en 1. Esto se debe a que hay 1 forma de hacer el número 0, usando 0 monedas.
Entonces, si comenzamos a iterar a través de toda la array de monedas y comparamos los elementos con la array de formas, determinaremos cuántas veces se puede usar una moneda para hacer los valores en el índice de la array de formas.
Por ejemplo…
Primero establece formas[0] = 1.
Comparemos la primera moneda, 1 centavo.
N = 12 Index of Array of Coins: [0, 1, 2] Array of coins: [1, 5, 10] Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Then compare coins[0] to all of the index's of ways array. If the value of the coin is less than or equal to the ways index, then ways[j-coins[i]]+ways[j] is the new value of ways[j]. We do this because we are trying to break each part down into smaller pieces. You will see what is happening as you continue to read. So comparing each value of the ways index to the first coin, we get the following. Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Comparemos ahora la segunda moneda, 5 centavos.
N = 12 Index of Array of Coins: [0, 1, 2] Array of coins: [1, 5, 10] Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Comparing 5 cents to each of the index and making that same comparison, if the value of the coin is smaller than the value of the index at the ways array then ways[j-coins[i]]+ways[j] is the new value of ways[j]. Thus we get the following. Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3] We are determining how many times the second coin goes into all of the values leading up the Nth coin. Why are we using all of the coins? It is to check our previous result dynamically and update our answer instead of recalculating all over again. For example take the element at index 10 the answer is 3 so far. But how did we get 3? We know that the value of 10-5 is 5 so that is our j-coins[i] value, that is the difference of what needs to be made up to make the amount 10. So we look at index 5 of the ways array and see it has the value 2, for the same reason as above, there are so far 2 ways to obtain the value 5. So if there are 2 ways to obtain the value 5 then those ways plus the current number of ways is the new updated value of the TOTAL ways to get the value at index 10.
Comparemos ahora la tercera moneda, 10 centavos.
N = 12 Index of Array of Coins: [0, 1, 2] Array of coins: [1, 5, 10] Comparing 10 cents to each of the index and making that same comparison, if the value of the coin is smaller than the value of the index at the ways array then ways[j-coins[i]]+ways[j] is the new value of ways[j]. Thus we get the following. Index of Array of ways: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Array of ways: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4] So the answer to our example is ways[12] which is 4.
Con todo lo anterior en mente, echemos un vistazo al siguiente programa a continuación.
C++
#include <bits/stdc++.h>
using namespace std;
/* We have input values of N and an array Coins
that holds all of the coins. We use data type
of long because we want to be able to test
large values
without integer overflow*/
long getNumberOfWays(long N, vector<long> Coins)
{
// Create the ways array to 1 plus the amount
// to stop overflow
vector<long> ways(N + 1);
// Set the first way to 1 because its 0 and
// there is 1 way to make 0 with 0 coins
ways[0] = 1;
// Go through all of the coins
for(int i = 0; i < Coins.size(); i++)
{
// Make a comparison to each index value
// of ways with the coin value.
for(int j = 0; j < ways.size(); j++)
{
if (Coins[i] <= j)
{
// Update the ways array
ways[j] += ways[(j - Coins[i])];
}
}
}
// Return the value at the Nth position
// of the ways array.
return ways[N];
}
void printArray(vector<long> coins)
{
for(long i : coins)
cout << i << "\n";
}
// Driver Code
int main()
{
vector<long> Coins = { 1, 5, 10 };
cout << "The Coins Array:" << endl;
printArray(Coins);
cout << "Solution:" << endl;
cout << getNumberOfWays(12, Coins) << endl;
}
// This code is contributed by mohit kumar 29
Java
/* We have input values of N and an array Coins
that holds all of the coins. We use data type
of long because we want to be able to test
large values
without integer overflow*/
class getWays {
static long getNumberOfWays(long N, long[] Coins)
{
// Create the ways array to 1 plus the amount
// to stop overflow
long[] ways = new long[(int)N + 1];
// Set the first way to 1 because its 0 and
// there is 1 way to make 0 with 0 coins
ways[0] = 1;
// Go through all of the coins
for (int i = 0; i < Coins.length; i++) {
// Make a comparison to each index value
// of ways with the coin value.
for (int j = 0; j < ways.length; j++) {
if (Coins[i] <= j) {
// Update the ways array
ways[j] += ways[(int)(j - Coins[i])];
}
}
}
// return the value at the Nth position
// of the ways array.
return ways[(int)N];
}
static void printArray(long[] coins)
{
for (long i : coins)
System.out.println(i);
}
public static void main(String args[])
{
long Coins[] = { 1, 5, 10 };
System.out.println("The Coins Array:");
printArray(Coins);
System.out.println("Solution:");
System.out.println(getNumberOfWays(12, Coins));
}
}
Python3
''' We have input values of N and an array Coins
that holds all of the coins. We use data type
of because long we want to be able to test
large values
without integer overflow'''
def getNumberOfWays(N, Coins):
# Create the ways array to 1 plus the amount
# to stop overflow
ways = [0] * (N + 1);
# Set the first way to 1 because its 0 and
# there is 1 way to make 0 with 0 coins
ways[0] = 1;
# Go through all of the coins
for i in range(len(Coins)):
# Make a comparison to each index value
# of ways with the coin value.
for j in range(len(ways)):
if (Coins[i] <= j):
# Update the ways array
ways[j] += ways[(int)(j - Coins[i])];
# return the value at the Nth position
# of the ways array.
return ways[N];
def printArray(coins):
for i in coins:
print(i);
if __name__ == '__main__':
Coins = [1, 5, 10];
print("The Coins Array:");
printArray(Coins);
print("Solution:",end="");
print(getNumberOfWays(12, Coins));
# This code is contributed by 29AjayKumar
C#
/* We have input values of N and
an array Coins that holds all of
the coins. We use data type of
long because we want to be able
to test large values without
integer overflow*/
using System;
public class getWays
{
static long getNumberOfWays(long N, long[] Coins)
{
// Create the ways array to 1 plus the amount
// to stop overflow
long[] ways = new long[(int)N + 1];
// Set the first way to 1 because its 0 and
// there is 1 way to make 0 with 0 coins
ways[0] = 1;
// Go through all of the coins
for (int i = 0; i < Coins.Length; i++)
{
// Make a comparison to each index value
// of ways with the coin value.
for (int j = 0; j < ways.Length; j++)
{
if (Coins[i] <= j)
{
// Update the ways array
ways[j] += ways[(int)(j - Coins[i])];
}
}
}
// return the value at the Nth position
// of the ways array.
return ways[(int)N];
}
static void printArray(long[] coins)
{
foreach (long i in coins)
Console.WriteLine(i);
}
// Driver code
public static void Main(String []args)
{
long []Coins = { 1, 5, 10 };
Console.WriteLine("The Coins Array:");
printArray(Coins);
Console.WriteLine("Solution:");
Console.WriteLine(getNumberOfWays(12, Coins));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
/* We have input values of N and an array Coins
that holds all of the coins. We use data type
of long because we want to be able to test
large values
without integer overflow*/
function getNumberOfWays(N,Coins)
{
// Create the ways array to 1 plus the amount
// to stop overflow
let ways = new Array(N + 1);
for(let i=0;i<N+1;i++)
{
ways[i]=0;
}
// Set the first way to 1 because its 0 and
// there is 1 way to make 0 with 0 coins
ways[0] = 1;
// Go through all of the coins
for (let i = 0; i < Coins.length; i++) {
// Make a comparison to each index value
// of ways with the coin value.
for (let j = 0; j < ways.length; j++) {
if (Coins[i] <= j) {
// Update the ways array
ways[j] += ways[(j - Coins[i])];
}
}
}
// return the value at the Nth position
// of the ways array.
return ways[N];
}
function printArray(coins)
{
for(let i=0;i<coins.length;i++)
{
document.write(coins[i]+"<br>");
}
}
let Coins=[1, 5, 10];
document.write("The Coins Array:<br>");
printArray(Coins);
document.write("Solution:<br>");
document.write(getNumberOfWays(12, Coins)+"<br>");
// This code is contributed by patel2127
</script>
The Coins Array: 1 5 10 Solution: 4
Publicación traducida automáticamente
Artículo escrito por Mohammad_Sarker y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA