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

Question

我正在尝试实施一个硬币问题，问题说明是这样的

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

 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。

任何人指导我如何实现这个？

原文由 Preetam Purbia 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以使用生成函数方法给出使用复数的快速算法。

给定硬币值c1，c2，..，ck，求和n的方法数，你需要的是x^n的系数

(1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...)

这与在中找到 x^n 的系数相同

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)

现在使用复数，x^a - 1 = (x-w1)(x-w2)…(x-wa) 其中 w1、w2 等是单位的复根。

所以

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)

可以写成

1/(x-a1)(x-a2)....(x-am)

可以使用部分分数重写为

A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am)

这里面x^n的系数很容易找到：

 A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1).

计算机程序应该能够轻松找到 Ai 和 ai（可以是复数）。当然，这可能涉及浮点计算。

对于大 n，这可能比枚举所有可能的组合更快。

希望有所帮助。

原文由 Aryabhatta 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

使用递归。

 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，有点生疏，所以可能会有些错误。

原文由 Jordi 发布，翻译遵循 CC BY-SA 3.0 许可协议