动态编程 - 改变 [英] Dynamic Programming - making change

问题描述

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

I'm having trouble figuring out my last section of code for a Dynamic Coin Changing Problem. I have included the code below.

我无法弄清楚最后一个 else 。我应该在那时使用贪婪算法，还是可以根据表中已有的值计算答案？我努力尝试理解这个问题，我觉得我很接近。该方法通过创建表并使用存储在表中的结果来解决较大的问题而不使用递归，从而找到进行特定更改所需的最小硬币数量。

I can't figure out the last else. Should I just use the greedy algorithm at that point or can I calculate the answer from values already in the table? I've worked hard on trying to understand this problem and I think I'm pretty close. The method finds the minimum amount of coins needed to make a certain amout of change by creating a table and using the results that are stored in the table to solve the larger problem without using recursion.

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

推荐答案

你不需要切换到贪婪算法来解决硬币变化问题，你可以用动态编程算法来解决它。例如，像这样：

You don't need to switch to a greedy algorithm for solving the coin changing problem, you can solve it with a dynamic programming algorithm. For instance, like this:

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

}

这篇关于动态编程 - 改变的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！