Programmazione dinamica - modifica apportata

Question

Non riesco a trovare la mia ultima sezione di codice per un problema di modifica dinamica delle monete. Ho incluso il codice qui sotto.

Non riesco a capire l'ultimo else. Dovrei semplicemente usare l'algoritmo greedy a quel punto o posso calcolare la risposta dai valori già presenti nella tabella? Ho lavorato duramente per cercare di capire questo problema e penso di essere abbastanza vicino. Il metodo trova la quantità minima di monete necessarie per creare una certa quantità di cambiamenti creando una tabella e usando i risultati che sono memorizzati nella tabella per risolvere il problema più grande senza ricorrere alla ricorsione.

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

Non è necessario passare a un algoritmo avido per risolvere il problema di cambio moneta, è possibile risolverlo con un algoritmo di programmazione dinamica. Per esempio, in questo modo:

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

Stai pensando troppo a questo? Se stessimo cercando di dare il cambio di 68 cent con monete USA ...

"negare" essere {25, 10, 5, 1}?

E la risposta non sarebbe "2 quarti, 1 centesimo, 1 nickel e 3 penny" = '2 + 1 + 1 + 3 = 7'? Quindi la funzione dovrebbe restituire il valore 7. Giusto?

Answer 3

Questo è in realtà la versione corretta di questo 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]; 

}