如何计数硬币的问题可能的组合 [英] How to count possible combination for coin problem

问题描述

我想实现一个硬币的问题，问题说明是这样的

I am trying to implement a coin problem, Problem specification is like this

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

Create a function to count all possible combination of coins which can be used for given amount.

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.

assume that coin array is sorted. for above example this function should return 6.

任何人指导我如何实现这种??

Anyone guide me how to implement this??

推荐答案

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

You can use generating function methods to give fast algorithms, which use complex numbers.

由于硬币值C1，C2，...，CK，获得的方法，总结N，你所需要的数量为x ^ n的系数

Given the coin values c1, c2, .., ck, to get the number of ways to sum n, what you need is the coefficient of x^n in

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

这是一样的发现X ^ n的系数

Which is the same as finding the coefficient of x^n in

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

现在使用复数，X ^一 - 1 =（X-W1）（X-W2）...（X-WA），其中W1，W2等都是统一的复根

Now using complex numbers, x^a - 1 = (x-w1)(x-w2)...(x-wa) where w1, w2 etc are the complex roots of unity.

于是

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

可以写成

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

可以使用部分分数被改写为

which can be rewritten using partial fractions are

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

X ^ n个在这个系数可以很容易地发现：

The coefficient of x^n in this can be easily found:

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

一个计算机程序，应该很容易就能找到爱和AI（可以是复数）。当然，这可能涉及浮点运算。

A computer program should easily be able to find Ai and ai (which could be complex numbers). Of course, this might involve floating point computations.

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

For large n, this will be probably faster than enumerating all the possible combinations.

希望有所帮助。

这篇关于如何计数硬币的问题可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！