用蛮力解决问题

Question

我有一些代码可以强行解决以下问题：

给定一套x硬币和一笔目标金额，达到该目标所需的硬币数量最少是多少？

到目前为止，守则：

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
    public static int min = Integer.MAX_VALUE;
    public static int[] combination;
    public static final int TARGET = 59;

    public static void main(String[] args) {
        long start = System.nanoTime();

        int[] validCoins = new int[] {1, 2, 5, 10, 20};
        Arrays.sort(validCoins);
        int len = validCoins.length;

        ArrayList<Integer> maxList = new ArrayList<Integer>();
        for(int c : validCoins) {
            maxList.add(TARGET / c);
        }

        int[] max = new int[len];
        for(int i = 0; i < len; i++) {
            max[i] = maxList.get(i).intValue();
        }

        permutations(new int[len], max, validCoins, 0); // bread&butter

        if(min != Integer.MAX_VALUE) {
            System.out.println();
            System.out.println("The combination " + Arrays.toString(combination) + " uses " + min + " coins to make the target of: " + TARGET);
        } else {
            System.out.println("The target was not reachable using these coins");
        }

        System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms");
    }

    public static void permutations(int[] workspace, int[] choices, int[] coins, int pos) {
        if(pos == workspace.length) {
            int sum = 0, coinCount = 0;
            System.out.println("TRYING " + Arrays.toString(workspace));
            for(int a = 0; a < coins.length; a++) {
                sum += workspace[a] * coins[a];
                coinCount += workspace[a];
            }
            if(sum == TARGET) {
                // System.out.println(Arrays.toString(n)); //valid combinations
                if(coinCount < min) {
                    min = coinCount;
                    combination = workspace;
                    System.out.println(Arrays.toString(combination)+" uses " + min + " coins");
                }
            }
            return;
        }
        for(int i = 0; i <= choices[pos]; i++) {
            workspace[pos] = i;
            permutations(workspace, choices, coins, pos + 1);
        }
    }
}

此解决方案使用递归。在Java中有使用循环计算组合的方法吗？

该算法还可以做哪些其他改进？

Answer 1

你的代码很复杂。让它变得如此复杂的是，您有递归调用与全局对象交互。这使得我们几乎不可能理解某一特定时刻的状态。

当您以递归方式编写算法时，您的目标应该是使(最小数量的)信息只通过方法参数(而不是任何全局状态)向一个方向传递，并使用返回值返回答案。

话虽如此，我们还是来看看如何使这件事奏效吧。

这个想法在这里非常简单：

如果我要用1，2，5，10，20达到59，我可以试着用0乘以20，看看如何用1，2，5，10达到59。我也可以尝试1乘20，看看如何用1，2，5，10达到剩下的39。我也可以试着用2乘20，看看我怎么能达到19，剩下的1，2，5，10。

我把解决这个问题简化为解决较小的问题(因为我们的硬币数量较少)。问题是“我什么时候才能停下来?”如果你已经达到目标，你可以停下来。如果你没有硬币可以尝试，你可以停止；

一旦用代码表示了这一点，就可以编写：

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
    public static final int TARGET = 59;

    public static void main(String[] args) {
        long start = System.nanoTime();

        int[] validCoins = new int[] {1, 2, 5, 10, 20};
        Arrays.sort(validCoins);

        int min = permutations(TARGET, validCoins);
        System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms to find " + min);
    }

    public static int permutations(int target, int[] coins) {
        return permutations(target, coins, coins.length);
    }

    public static int permutations(int target, int[] coins, int array_size) {
        System.out.println("TRYING " + target + " with " + array_size + " different coins");
        assert target >= 0;
        assert array_size >= 0;
        assert array_size <= coins.length;
        if (target==0) // target is reached (in 0 coin)
            return 0;
        if (array_size == 0) // no more coins to reach a positive target
            return -1;
        array_size--;
        int coin = coins[array_size]; // let's consider the biggest coin
        int nb = target/coin; // and check how many times it fits in the target
        int sol = -1; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
        for (int i = 0; i <= nb; i++) // let's try all possible values
        {
            // to check if we can reach the target with the other coins
            int sol_cand = permutations(target - i * coin, coins, array_size);
            if (sol_cand >= 0) // if we did
            {
                if (sol == -1 || sol_cand + i < sol) // and the new solution is better
                    sol = sol_cand + i; // then we are happy
            }
        }
        return sol;
    }
}

这已经比你的例子快24倍了。

现在，您可以尝试添加优化。一个简单的优化是说，如果你能用最大的硬币达到当前的目标，就没有必要更进一步，因为如果你使用较小的硬币，你将需要更多的硬币。

    int coin = coins[array_size]; // let's consider the biggest coin
    int nb = target/coin; // and check how many times it fits in the target
    if (nb * coin == target) // if it fits an exact number of time, we won't beat this
        return nb;

这使得这个例子的代码速度快了70倍。(如果这样做，检查target == 0是否不再相关，因为我们将始终拥有target > 0)。

另外，不是一个特定的优化，但是如果您想像以前一样在Integer.MAX_VALUE中使用，可以重写循环：

    int sol = Integer.MAX_VALUE; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
    for (int i = 0; i <= nb; i++) // let's try all possible values
    {
        sol = Math.min(sol, i + permutations(target - i * coin, coins, array_size));
    }

这件事就这么简单。然后，您可以编写单元测试，以检查您的代码是否以您想要的方式运行。最后，如果您愿意，可以考虑各种优化:使用缓存避免多次计算相同的事情，添加条件以更早地停止循环，等等。