丢人了，Projece Euler 上的第 31 问做了两天都还没搞定。不难啊，可脑子就是想不清楚，唉，老矣。
题目是这样的：
现有面值为1分、2分、5分、10分、20分、50分、1磅（100分）、2磅（200分）的硬币，问2磅钱可以有多少种兑换方案？
这是经典的找零钱问题。
我是这么考虑的，既然要求所有的兑换方案，那我只要把问题规约到这些面额组成的集合的子集上就行了。当我用某一子集来兑换时，该子集上的每种硬币至少含1枚。 我们来看个简化的实例：现有1分、2分和5分三种硬币，兑换10分钱有多少种方法？
- 当我们去集合
{1, 2, 5}时，因为5+2+1已经是 8 了，故只要再加上2的方案，即，5+2+2+1,5+2+1+1+1； - 当我们去集合
{2, 5}时，因为5+2=7，而 3 不可能用{2, 5}的整数线性组合来得到，故在这种情况下不存在兑换方案； - 当我们去集合
{1, 5}时，方案为：5+1+1+1+1+1； - 当我们去集合
{1, 2}时，方案为：2+2+2+2+1+1,2+2+2+1+1+1+1,2+2+1+1+1+1+1+1,2+1+1+1+1+1+1+1+1； - 当我们去集合
{5}时，方案为：5+5； - 当我们去集合
{2}时，方案为：2+2+2+2+2； - 当我们去集合
{1}时，方案为：1+1+1+1+1+1+1+1+1+1；
共 10 种方案。
递归解法
但其实不用这么麻烦，设可选的硬币面值分别为{S_1, S_2, ..., S_m}，用这些面额的硬币来兑换n分钱有count(n, {S_1, S_2, ..., S_m})种方法。有两种不同的兑换方式：
- 兑换的硬币面额中没有
S_m，即count(n, {S_1, S_2, ..., S_{m-1}})； - 兑换的零钱中至少有一枚
S_m分的硬币，即count(n-S_m, {S_1, S_2, ..., S_m})。
可我有个疑问，对于第二种情况，count(n-S_m, {S_1, S_2, ..., S_m})真的能代表包含S_m分硬币的所有方案吗？我们需要论证，在只使用{S_1, S_2, ..., S_m}硬币时，含S_m分硬币的n分兑换方案数不比n-S_m分的少。
用反证法，如果n-S_m分的方案数比n分的多，那么在多的那些方案中添上一枚S_m分硬币即可得到新的兑换方案，矛盾。同样，如果n-S_m分的方案数比n分的少，那么在n分兑换方案中多的那些方案中剔除一枚S_m分硬币（这些方案至少有一枚S_m分硬币）即可得到新n-S_m分兑换方案，也矛盾。
这里还隐含了：count(S_m-S_m, {S_1, S_2, ..., S_m}) = 1
还是那个例子：
1-
2,1+1 -
2+1,1+1+1 -
2+2,2+1+1,1+1+1+1 -
5,2+2+1,2+1+1+1,1+1+1+1+1 -
5+1,2+2+2,2+2+1+1,2+1+1+1+1,1+1+1+1+1+1 -
5+2,5+1+1,2+2+2+1,2+2+1+1+1,2+1+1+1+1+1,1+1+1+1+1+1+1 -
5+2+1,5+1+1+1,2+2+2+2,2+2+2+1+1,2+2+1+1+1+1,2+1+1+1+1+1+1,1+1+1+1+1+1+1+1 -
5+2+2,5+2+1+1,5+1+1+1+1,2+2+2+2+1,2+2+2+1+1+1,2+2+1+1+1+1+1,2+1+1+1+1+1+1+1,1+1+1+1+1+1+1+1+1 -
5+5,5+2+2+1,5+2+1+1+1,5+1+1+1+1+1,2+2+2+2+2,2+2+2+2+1+1,2+2+2+1+1+1+1,2+2+1+1+1+1+1+1,2+1+1+1+1+1+1+1+1,1+1+1+1+1+1+1+1+1+1
以 6 为例，兑换方案分为两组：
一组是6中不含{5}的兑换方案：2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1；
一组是6 - 5的兑换方案加上5：1+5；
生成函数解法
另一种思路来自生成函数：
要想知道为什么系数就是兑换方案的种数，请参阅：組合數學中的生成函數、什么是生成函数？
Mathematica代码：
最后给几个作弊招数：
Length@FrobeniusSolve[{1,2,5,10,20,50,100,200},200]
Length[IntegerPartitions[200, All, {1, 2, 5, 10, 20, 50, 100, 200}]]
Length[Reduce[
1*a + 2*b + 5*c + 10*d + 20*e + 50*f + 100*g + 200*h == 200 &&
a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 &&
g >= 0 && h >= 0, {a, b, c, d, e, f, g, h}, Integers]]
P.S. CSDN 的编辑器实在太烂了-_-！
网友评论