如何计算硬币问题的可能组合

algorithm java combinations

2022-09-01 12:37:13

我正在尝试实现一个硬币问题，问题规范是这样的

创建一个函数来计算可用于给定金额的所有可能的硬币组合。

All possible combinations for given amount=15, coin types=1 6 7 
1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2) 1,1,1,1,1,1,1,1,1,6,
3) 1,1,1,1,1,1,1,1,7,
4) 1,1,1,6,6,
5) 1,1,6,7,
6) 1,7,7,

函数原型：

int findCombinationsCount(int amount, int coins[])

假设硬币数组已排序。对于上面的示例，此函数应返回 6。

有人指导我如何实现这一点？？

答案 1

使用递归。

int findCombinationsCount(int amount, int coins[]) {
    return findCombinationsCount(amount, coins, 0);
}

int findCombinationsCount(int amount, int coins[], int checkFromIndex) {
    if (amount == 0)
        return 1;
    else if (amount < 0 || coins.length == checkFromIndex)
        return 0;
    else {
        int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex);
        int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1);
        return withFirstCoin + withoutFirstCoin;
    }
}

不过，您应该检查此实现。我这里没有Java IDE，而且我有点生锈，所以它可能有一些错误。

答案 2

虽然递归可以工作，并且通常是在一些关于算法和数据结构的大学课程中实现的任务，但我相信“动态规划”实现更有效。

public static int findCombinationsCount(int sum, int vals[]) {
        if (sum < 0) {
            return 0;
        }
        if (vals == null || vals.length == 0) {
            return 0;
        }

        int dp[] = new int[sum + 1];
        dp[0] = 1;
        for (int i = 0; i < vals.length; ++i) {
            for (int j = vals[i]; j <= sum; ++j) {
                dp[j] += dp[j - vals[i]];
            }
        }
        return dp[sum];
    }