通过蛮力的爪哇硬币组合

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

我发现了一种动态规划方法，这种方法肯定没有得到优化，但如果有人感兴趣的话，对于目标数字高达10000也不算太坏

import java.util.*;

public class coinSumMinimalistic {
    public static final int TARGET = 12003;
    public static int[] validCoins = {1, 3, 5, 6, 7, 10, 12};

    public static void main(String[] args) {
        Arrays.sort(validCoins);

        sack();
    }

    public static void sack() {
        Map<Integer, Integer> coins = new TreeMap<Integer, Integer>();
        coins.put(0, 0);
        int a = 0;
        for(int i = 1; i <= TARGET; i++) {
            if(a < validCoins.length && i == validCoins[a]) {
                coins.put(i, 1);
                a++;
            } else coins.put(i, -1);
        }
        for(int x = 2; x <= TARGET; x++) {
            if(x % 5000 == 0) System.out.println("AT: " + x);
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i <= x / 2; i++) {
                int j = x - i;
                list.add(i);
                list.add(j);
            }
            coins.put(x, min(list, coins));
        }
        System.out.println("It takes " + coins.get(TARGET) + " coins to reach the target of " + TARGET);
    }

    public static int min(ArrayList<Integer> combos, Map<Integer, Integer> coins) {
        int min = Integer.MAX_VALUE;
        int total = 0;
        for(int i = 0; i < combos.size() - 1; i += 2) {
            int x = coins.get(combos.get(i));
            int y = coins.get(combos.get(i + 1));
            if(x < 0 || y < 0) continue;
            else {
                total = x + y;
                if(total > 0 && total < min) {
                    min = total;
                }
            }
        }
        int t = (min == Integer.MAX_VALUE || min < 0) ? -1:min;
        return t;
    }

    public static void print(Map<Integer, Integer> map) {
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println("[" + entry.getKey() + ", " + entry.getValue() + "]");
        }
        System.out.println();
    }
}

Answer 2

这里是python中的一个解决方案，它使用动态编程来找到达到目标值的最小硬币数

该算法的工作原理如下

dp[i][target] = minimum number of coins required required to acheive target using first i coin
dp[i][target] = min(dp[i-1][target],dp[i-1][target-coin[i]]+1)
dp[i-1][target] denotes not using the ith coin
dp[i-1][target-coin[i]] denotes making use of ith coin

因为对于每一枚硬币，你都在检查是否包含它，所以算法会枚举所有可能的组合

这是上述算法的空间优化版本

maxvalue = 10 ** 9
def minchange(coins, target):
    no_of_coins = len(coins)
    dp = [maxvalue for i in range(target + 1) ]
    dp[0] = 0
    for i in range(no_of_coins):
        for j in range(coins[i], target + 1):
            dp[j] = min(dp[j], dp[j - coins[i]] + 1)
    return dp[target]

Answer 3

您可以对硬币阵列进行排序。然后从右向左，不断从目标值中减去，直到硬币从目标的剩余值中变大。在硬币阵列中向左移动并重复此过程

例如：

{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