如何计算硬币问题的可能组合
我正在尝试实现一个硬币问题，问题说明如下
创建一个函数来计算所有可能的硬币组合，这些组合可以用于给定的金额。
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。
有没有人教我怎么实现这个？？
Stack Overflow用户
发布于 2014-09-12 00:21:44
用于计算固定面额硬币找零的方法数量的Aryabhatta’s answer非常可爱，但实现起来也不切实际。我们不使用复数，而是使用模算术，类似于数论变换如何取代傅立叶变换来乘以整数多项式。
设D是硬币面额的最小公倍数。根据狄利克雷关于算术级数的定理，存在无穷多个素数p使得D除以p - 1。(如果幸运的话，它们甚至会以一种我们可以高效找到它们的方式进行分发。)我们将计算对满足此条件的一些p取模的方法的数量。通过以某种方式获得一个粗略的界限(例如，选择k - 1，其中n是总数，k是面额的数量)，对乘积超过这个界限的几个不同的素数重复这个过程，并应用中国剩余定理，我们可以恢复确切的数字。
测试整数k > 0的候选者1 + k*D，直到我们找到一个素数p。假设g是模为p的原根(随机生成候选并应用标准测试)。对于每个面额的d，将多项式x**d - 1模p表示为因子的乘积：
x**d - 1 = product from i=0 to d-1 of (x - g**((p-1)*i/d)) [modulo p].注意，d除以D除以p-1，所以指数确实是一个整数。
设m为面额之和。将所有常量g**((p-1)*i/d)收集为a(0), ..., a(m-1)。下一步是找到部分分数分解A(0), ..., A(m-1)，使得
sign / product from j=0 to m-1 of (a(j) - x) =
sum from j=0 to m-1 of A(j)/(a(j) - x) [modulo p],其中，如果面额为偶数，则sign为1；如果面额为奇数，则为-1。通过对给定方程的两边计算不同的x值，导出A(j)的线性方程组，然后用高斯消元法求解。如果有重复，生活就会变得复杂；选择另一个素数可能是最简单的。
给定此设置，我们可以计算出使更改等于n的方法(当然是模数p )的数量为
sum from j=0 to m-1 of A(j) * (1/a(j))**(n+1).https://stackoverflow.com/questions/4243831
复制相似问题
腾讯云开发者
