java - 通过暴力破解硬币组合

Question

我有一些代码可以强力解决以下问题:

Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target?

到目前为止的代码:

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}
num = 59

Try coins from right to left:
59 - 20 = 39
So far coins used [20]

39 - 20 = 19
So far coins used [20,20]

19 - 20 = -1, Can't use 20!
19 - 10 = 9
So far coins used [20,20,10]

9 - 10 = -1, Can't use 10!
9 - 5 = 4
So far coins used [20,20,10,5]

4 - 5 = -1, Can't use 5!
4 - 2 = 2
So far coins used [20,20,10,5,2]

2 - 2 = 0
So far coins used [20,20,10,5,2,2]
Total coin used 6