动态编程 – 改变
我在查找动态硬币更改问题的最后一段代码时遇到了麻烦。 我已经包含了以下代码。
我无法弄清楚最后的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 = 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]; }
您无需切换到贪婪算法来解决硬币更改问题，您可以使用动态编程算法来解决它。 例如，像这样：
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]; }
//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]; }
你是在想这个吗？ 如果我们试图用美国硬币给出68美分的变化……
‘denom’会{25,10,5,1}吗？
答案不是“2个季度，1个角钱，1个镍币和3个硬币”=“2 + 1 + 1 + 3 = 7”？ 所以函数应该返回值7.对吧？
这实际上是此算法的正确版本。
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]; }