Determinar las combinaciones de hacer cambios para una cantidad dada

Question

Mi tarea es escribir un algoritmo usando la fuerza bruta para determinar el número de formas distintas, una combinación relacionada de cambio para la cantidad dada. El cambio se producirá utilizando las siguientes monedas: centavo (1 centavo), níquel (5 centavos), moneda de 10 centavos (10 centavos) y cuarto (25 centavos).

p. Ej.

de entrada: 16 (que significa un cambio de 16 centavos)

salida: puede ser producido en 6 maneras diferentes y son:

1. 16 peniques.
2. 11 peniques, 1 níquel
3. 6 centavos, 1 moneda de diez centavos
4. 6 centavos, 2 monedas de cinco centavos
5. 1 centavo, 3 monedas de cinco centavos
6. 1 centavo, 1 níquel, 1 moneda de diez centavos

Mi Algoritmo debe producir todas las combinaciones de cambio posibles para una cantidad especificada de cambio.

---

Estoy en una pérdida completa en cuanto a cómo incluso comenzar a comenzar un algoritmo como este. Cualquier aporte o idea para ponerme en marcha sería increíble.

Answer 1

Ok. Déjame explicar una idea para un algoritmo de fuerza bruta. Usaré la recursión aquí.

Vamos a necesitar un cambio de c centavos. Entonces considere c como

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER 

o, simplemente,

c = (p * 1) + (n * 5) + (d * 10) + (q * 25) 

Ahora tiene que ir a través de todos los valores posibles para p, n, d y q que es igual al valor de c. Usando recursion, para cada p in [0, maximumPennies] pase por cada n in [0, maximumNickels]. Para cada n pase por cada d in [0, maximumDimes]. Para cada d pase por cada q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p 
    | 
    +- n in [0, maximumNickels] AND c >= p + 5n 
     | 
     +- d in [0, maximumDimes] AND c >= p + 5n + 10d 
      | 
      +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q 

Para cualquier igualdad en estos pasos, usted tiene una solución.

Answer 2

Intente utilizar recursividad en este caso. Su función debe tomar dos parámetros: el valor máximo que puede usar y el monto restante para pagar (necesita el primero para evitar la repetición). Realice la función de tal manera: si se trata de un caso trivial (por ejemplo, 1, 5, 10 y se le permite tomar un centavo, cinco centavos, diez centavos, respectivamente) imprima la solución trivial. Además, para cada caso trate de tomar una moneda de todos los tipos permitidos (por ejemplo, no mayor que el máximo permitido) y continúe de forma recursiva.

Espero que esto ayude.

Answer 3

Podría comenzar a pensar en este problema dividiéndolo en sub-problemas para resolverlos y luego cambiar el problema y ajustar su solución.

En su caso, primero podría tratar de resolver el problema usando solo centavos (con una sola solución obvia por supuesto), luego mire las monedas de cinco centavos y mire todas las combinaciones allí y así sucesivamente. Para mejorar esto, puede reutilizar soluciones de etapas anteriores en su algoritmo.

Answer 4

Bueno, si quieres una solución de fuerza bruta, puedes comenzar con un recursive approach muy ingenuo. Pero para ser eficiente, necesitarás un dynamic programming approach.

Para el enfoque recursivo:

1. find out the number of ways you can make using penny only. 
2. do the same using penny and nickel only. (this includes step 1 also) 
3. the same using penny, nickel and dime only (including step 2). 
4. using all the coins (with all previous steps). 

Paso 1 es sencillo, sólo una manera de hacerlo.

Para el paso 2, la recursión debe ser así:

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel 
    + number of ways to make n cent using penny only 

Paso 3:

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime 
    + number of ways to make n cent using penny and nickel only 

Paso 4 es similar.

Y una cosa para recordar: usted puede hacer 0 ciento en uno manera (es decir, el uso de las monedas cero), que es el caso base.

Answer 5

public class PrintAllCoinCombinations { 


    static int findChange(int arr[], int index , int value, String str){ 

     if(value == 0){ 
      System.out.println(str); 
      return 1; 
     } 
     if(index<0){ 
      return 0; 
     } 
     if(value<0){ 
      return 0; 
     } 

     int excl = findChange(arr,index-1,value,str); 

     str += " "+ arr[index]; 

     int incl = findChange(arr,index,value-arr[index],str); 

     return incl + excl; 

    } 

    public static void main(String [] arg){ 
     int arr[] = {1,5,10,25}; 
     String s = ""; 
     int result = findChange(arr,3,16,s); 
     System.out.println(result); 
    } 
}