1

所以我写了一个递归算法来解决一个问题，即找出一组特定面额的“硬币”的最少数量，以达到给定的总和。该算法似乎有效，但因为它是递归的，并且在选择一个或另一个之前计算每个可能的选项，我很难想出一种方法来打印出所使用的面额。所以基本上我可以计算出可能使用的最少硬币数量，但不能计算它们是哪些硬币。这是我用来驱动它的代码和小主要方法。任何简化算法本身的建议也将受到欢迎。

public class DynamicCoinChange {

    public static void main(String[] args) {
        int[] denoms = {1, 6, 10, 25};
        int numCoins = dynamicCoinChange(denoms, 18, 3);
        System.out.println(numCoins);
    }

    public static int dynamicCoinChange(int[] denoms, int amt, int start) {
        if (amt == 0 || start < 0) {
            return 0;
        } else if (amt == 1) {
            return 1;
        } else if (denoms[start] > amt || 
                dynamicCoinChange(denoms, amt, start-1) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start)) &&
                !(dynamicCoinChange(denoms, amt, start-1) == 0)) {
            return dynamicCoinChange(denoms, amt, start-1);
        } else {
            return 1 + dynamicCoinChange(denoms,amt-denoms[start], start);
        }
    }
}
4

2 回答 2

0

最小变化问题不需要递归编程。它可以以更简单的迭代方式进行编程。

int[] denoms = { 1, 6, 10, 25 };
int amt = 18;
double[] min = new double[ amt + 1 ];

for( int i = 1; i < min.length; i++ ) { // We're keeping min[ 0 ] as 0/
    min[ i ] = Double.POSITIVE_INFINITY;
}

for( int i = 1; i <= amt; i++ ) {

   for( int j = 0; j <= N - 1; j++ ) {

       if( denoms[ j ] <= i && min[ i - denoms[ j ] ] + 1 < min[ i ] )
           min[ i ] = min[ i - denoms[ j ] ] + 1;

   }
}

在这里，您的解决方案将在条目 min[amt] 中。

于 2013-03-17T03:11:39.903 回答
0

我们需要知道两条信息：

  • when a coin is chosen for the optimal solution
  • 选择哪个硬币作为最佳解决方案

根据您的算法，我们知道每当您返回时，我们都会选择一枚硬币1。我们也知道在选择的硬币指数为 时选择的硬币start。因此，我们有信息可以解决这个问题。

由于性能在这里不是问题，我们将简单地传递一个硬币参数，该参数在选择硬币时填充。

public static int dynamicCoinChange(int[] denoms, int amt, int start, ArrayList<Integer> coins) {
    if (amt == 0 || start < 0) {
        return 0;
    } else if (amt == 1) {
        coins.add(1);
        return 1;
    } else if (denoms[start] > amt 
            // Note that these calls are not guaranteed to be in our solution
            // Thus, we make a copy to prevent the calls from modifying our solution
            || dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start, new ArrayList<Integer>(coins))) 
            && !(dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) == 0)) {
        return dynamicCoinChange(denoms, amt, start-1, coins);
    } else {
        coins.add(denoms[start]);
        return 1 + dynamicCoinChange(denoms,amt-denoms[start], start, coins);
    }
}

由于这需要我们更改方法签名，因此我们还必须修改我们的驱动程序：

public static void main(String[] args) {
    int[] denoms = {1, 6, 10, 25};
    ArrayList<Integer> coins = new ArrayList<Integer>();
    int numCoins = dynamicCoinChange(denoms, 7, 3, coins);
    for (Integer coin : coins)
        System.out.println(coin);
    System.out.println(numCoins);
}

在递归调用结束时，coins应包含按时间顺序选择的硬币列表。

于 2013-03-17T03:12:19.130 回答