凑 40 元问题

March 28, 2024

有这样一个问题：有 1 元、2 元、5 元和 10 元纸币各无数张，凑出 40 元，共有几种方案？

最简单直接的方法就是硬算。可以按面值的选择方式分类，再分别去计算各种情况。

面值选择	方案数
单一币种	4
5元，10元	3
2元，10元	3
2元，5元	3
1元，10元	3
1元，5元	7
1元，2元	19
2元，5元，10元	3
1元，5元，10元	9
1元，2元，10元	27
1元，2元，5元	65
1元，2元，5元，10元	49

后面几种组合方案算起来还是比较麻烦的。这种硬算的方法耗时较长，容易出错。最要命的是，有多次重复计算。作为一个对计算机算法有一点皮毛了解的人，这种重复计算自然是不能忍受的。于是开始思考效率更高的算法。

对于特定目标值的组合方案数，可以分成以下两类：包含最大面值的与不包含最大面值的。以上面这道题为例，用 1、2、5、10 元凑 40 元的方案可以分为：包含 10 元的和不包含 10 元的。这样就形成了递归。

x[i]=[1, 2, 5, 10]

count (a, b)
    if a<0 return 0
    if a=0 return 1
    if b=1 return count(a-x[1], 1)
    return count(a, b-1) + count(a-x[b], b)

上面这个算法，x 为允许使用的面值数组，必须按照递增顺序排列。下标从 1 开始，即 x₁=1, x₂=2, x₃=5, x₄=10。 count(a,b) 表示用前 b 种面值凑 a 元的方案数。注意当 a 等于 0 时，函数要返回 1，这是符合递归规律的正确结果。对于凑 40 元问题，即求出 count(40, 4)。数值不大，所以我们可以用手算来复现计算机算法的计算过程。

flowchart TD
    A["(40, 4)"]
    B1["(40, 3)"]
    B2["(30, 4)"]
    A --> B1
    A --> B2
    C1["(40, 2)"]
    C2["(35, 3)"]
    C3["(30, 3)"]
    C4["(20, 4)"]
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    D1["(35, 2)"]
    D2["(30, 3)"]
    D3["(20, 3)"]
    D4["(10, 4)"]
    C2 --> D1
    C2 --> D2
    C4 --> D3
    C4 --> D4
    E1["(30, 2)"]
    E2["(25, 3)"]
    E3["(10, 3)"]
    E4["(0, 4)"]
    D2 --> E1
    D2 --> E2
    D4 --> E3
    D4 --> E4
    F1["(25, 2)"]
    F2["(20, 3)"]
    E2 --> F1
    E2 --> F2
    G1["(20, 2)"]
    G2["(15, 3)"]
    F2 --> G1
    F2 --> G2
    H1["(15, 2)"]
    H2["(10, 3)"]
    G2 --> H1
    G2 --> H2
    I1["(10, 2)"]
    I2["(5, 3)"]
    H2 --> I1
    H2 --> I2
    J1["(5, 2)"]
    J2["(0, 3)"]
    I2 --> J1
    I2 --> J2

我们可以发现，第四层调用出现了 (30, 3)，与第三层的相同调用可以合并，后续的调用层中也出现了可以合并的相同调用。所以用这种方法，效率又高，又不易出错。