動態編程 - 製作變化

Question

我無法找出動態變幣問題的最後一段代碼。我已經包含下面的代碼。

我想不通最後的else。我應該在那一點使用貪婪算法還是可以根據表中已有值計算答案？我努力嘗試理解這個問題，我認爲我非常接近。該方法通過創建一個表並使用存儲在表中的結果來解決較大的問題而不使用遞歸來找到進行某種變化所需的最小硬幣數量。

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

您不需要切換到貪婪算法來解決硬幣更換問題，您可以使用動態編程算法來解決它。例如，像這樣：

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

你是否在想這個？如果我們試圖用美元硬幣兌換68美分......

'denom'是{25,10,5,1}嗎？

難道答案是「2個季度，1個硬幣，1個鎳和3個硬幣」='2 + 1 + 1 + 3 = 7'？所以函數應該返回值7.對嗎？

Answer 3

這實際上是該算法的正確版本。

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]; 

}