如何计算硬币问题的可能组合
如何计算硬币问题的可能组合
提问于 2010-11-22 17:10:31
我正在尝试实现一个硬币问题，问题说明如下
创建一个函数来计算所有可能的硬币组合，这些组合可以用于给定的金额。
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。
有没有人教我怎么实现这个？？
回答 17
Stack Overflow用户
回答已采纳
发布于 2010-11-23 03:08:25
您可以使用生成函数方法来给出使用复数的快速算法。
给定硬币值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，这可能比枚举所有可能的组合更快。
希望这能有所帮助。
Stack Overflow用户
发布于 2010-11-22 17:24:05
使用递归。
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，而且我有点生疏了，所以它可能有一些错误。
Stack Overflow用户
发布于 2012-09-20 02:56:29
尽管递归可以工作，并且经常是一些关于算法和数据结构的大学级课程中要实现的任务，但我相信“动态编程”实现更有效。
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];
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4243831
复制相关文章
相似问题
腾讯云开发者
