6

我无法弄清楚动态硬币更换问题的最后一段代码。我已经包含了下面的代码。

我想不通最后一个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];
}
4

4 回答 4

2

您不需要切换到贪心算法来解决硬币兑换问题，您可以使用动态规划算法来解决它。例如，像这样：

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

}
于 2011-11-07T01:46:51.940 回答
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];

}
于 2013-09-15T00:16:44.017 回答
0

你是不是想太多了？如果我们试图用美国硬币给 68 美分找零……</p>

'denom' 会是 { 25, 10, 5, 1 } 吗？

答案会不会是“2 美分硬币、1 硬币、1 镍币和 3 便士”='2 + 1 + 1 + 3 = 7'？所以函数应该返回值 7。对吗？

于 2011-11-07T01:35:14.667 回答
0

这实际上是该算法的正确版本。

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];
}
于 2013-01-05T19:02:17.143 回答