Programación dinámica: cambio

Question

Tengo problemas para encontrar la última sección de código para un problema de cambio de moneda dinámica. He incluido el código a continuación.

No puedo entender el último else. ¿Debería usar el algoritmo codicioso en ese punto o puedo calcular la respuesta a partir de los valores que ya figuran en la tabla? He trabajado duro para tratar de entender este problema y creo que estoy bastante cerca. El método encuentra la cantidad mínima de monedas necesarias para hacer una cierta cantidad de cambios creando una tabla y usando los resultados que están almacenados en la tabla para resolver el problema más grande sin usar la recursión.

public static int minCoins(int[] denom, int targetAmount){ 
    int denomPosition; // Position in denom[] where the first spot 
         // is the largest coin and includes every coin 
         // smaller. 
    int currentAmount; // The Amount of money that needs to be made 
         // remainingAmount <= initalAmount 
    int[][] table = new int[denom.length][targetAmount+1]; 
    for(denomPosition = denom.length-1 ; denomPosition >= 0 ; denomPosition--) { 
     for(currentAmount = 0 ; currentAmount <= targetAmount ; currentAmount++){ 
      if (denomPosition == denom.length-1){ 
       table[denomPosition][currentAmount] = 
        currentAmount/denom[denomPosition]; 
      } 
      else if (currentAmount<denom[denomPosition]){ 
       table[denomPosition][currentAmount] = 
        table[denomPosition+1][currentAmount]; 
      } 
      else{   
       table[denomPosition][currentAmount] = 
        table[denomPosition+1][currentAmount]- 
        table[denomPosition][denom[denomPosition]]-1; 
      } 
     } 
    } 
    return table[0][targetAmount]; 
} 

Answer 1

No necesita cambiar a un algoritmo codicioso para resolver el problema del cambio de moneda, puede resolverlo con un algoritmo de programación dinámica. Por ejemplo, así:

public int minChange(int[] denom, int targetAmount) { 

    int actualAmount; 
    int m = denom.length+1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE-1; 

    int[][] table = new int[m][n]; 
    for (int j = 1; j < n; j++) 
     table[0][j] = inf; 

    for (int denomPosition = 1; denomPosition < m; denomPosition++) { 
     for (int currentAmount = 1; currentAmount < n; currentAmount++) { 
      if (currentAmount - denom[denomPosition-1] >= 0) 
       actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]]; 
      else 
       actualAmount = inf; 
      table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount); 
     } 
    } 

    return table[m-1][n-1]; 

} 

Answer 2

¿Estás pensando en esto? Si intentáramos cambiar 68 centavos usando monedas de EE. UU ...

¿Sería 'denom' ser {25, 10, 5, 1}?

¿Y la respuesta no sería "2 trimestres, 1 moneda de diez centavos, 1 moneda de cinco centavos y 3 centavos" = '2 + 1 + 1 + 3 = 7'? Entonces la función debería devolver el valor 7. ¿Correcto?

Answer 3

Esta es en realidad la versión correcta de este algoritmo.

public static int minChange(int[] denom, int targetAmount) { 
    int actualAmount; 
    int m = denom.length + 1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE - 1; 

    int[][] table = new int[m][n]; 
    for(int i = 0; i< m; ++i) { 
     for (int j = 1; j < n; j++) { 
      table[i][j] = inf; 
     } 
    } 

    for (int denomPosition = 1; denomPosition < m; denomPosition++) { 
     for (int currentAmount = 1; currentAmount < n; currentAmount++) { 
      if (denom[denomPosition-1] <= currentAmount) { 
       // take 
       actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]]; 
      } 
      else { 
       actualAmount = inf; 
      }            // do not take 
      table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount); 
     } 
    } 

    return table[m-1][n-1]; 
} 

Answer 4

//this works perfectly ... 

public int minChange(int[] denom, int targetAmount) 
    { 

    int actualAmount; 
    int m = denom.length+1; 
    int n = targetAmount + 1; 
    int inf = Integer.MAX_VALUE-1; 

    int[][] table = new int[m][n]; 
    for (int j = 1; j < n; j++) 
     table[0][j] = inf; 

    for (int i = 1; i < m; i++) //i denotes denominationIndex 
    { 
     for (int j = 1; j < n; j++) //j denotes current Amount 
     { 
      if (j - denom[i-1] >= 0)//take this denomination value and subtract this value from Current amount 

       table[i][j] = Math.min(table[i-1][j], 1 + table[i][j - denom[i-1]]); 

      else 
       table[i][j] = table[i-1][j]; 

     } 
    } 




    //display array 
     System.out.println("----------------Displaying the 2-D Matrix(denominations and amount)----------------"); 
     for (int i = 0; i < m; i++) 
     { 
      System.out.println(" "); 
      for (int j = 0; j < n; j++) 
      { 
       System.out.print(" "+table[i][j]); 

      } 
      System.out.println(" "); 
     } 

    return table[m-1][n-1]; 

}