纸币问题 3

题意

有 $n$ 种面额互不相同的纸币，第 $i$ 种面额为 $a_i$ ，每种无限张。要凑出金额 $w$ （ $1 \leqslant w \leqslant 10^4$ ），求纸币组合数。同样的纸币组合无论支付顺序如何，只算一种方案。答案对 $10^9+7$ 取模。

原题对象	背包含义
一种纸币	一个可以重复使用的物品
面额 $a_i$	物品体积
纸币组合	无序组合（多重集）
凑出金额 $w$	恰好装满容量 $w$

思路

一句话本质： 求完全背包的组合计数——先枚举纸币再枚举金额，强制编号顺序，把不同排列合并为同一种组合。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43// brute.cpp：小数据暴力解，递归枚举每种纸币的使用张数，统计组合数（顺序不同算同一种）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MOD = 1000000007;

int n;          // 纸币种类数
int w;          // 要凑出的金额
int a[MAXN];    // 每种纸币的面额
int answer;     // 方案数

// dep：当前正在决定第 dep 种纸币的使用张数
// remain：剩余需要凑出的金额
void dfs(int dep, int remain) {
    if (dep == n + 1) {
        if (remain == 0)
            answer = (answer + 1) % MOD;
        return;
    }

    // 枚举第 dep 种纸币用 cnt 张
    int max_cnt = remain / a[dep];
    for (int cnt = 0; cnt <= max_cnt; cnt++) {
        dfs(dep + 1, remain - cnt * a[dep]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    answer = 0;
    dfs(1, w);
    cout << answer << '\n';

    return 0;
}

这个暴力按纸币编号顺序，对每种纸币枚举使用张数。递归到叶子如果剩余金额恰好为 0，就找到一种组合。因为纸币是按编号顺序处理的，同一种组合只会被枚举一次。

这个暴力和纸币问题 2 的暴力有什么不同？

纸币问题 2 的暴力每次任选一张纸币继续递归，同一个组合会因支付顺序不同被枚举多次。本题暴力按编号顺序依次决定每种纸币的张数，天然保证了每种组合只被计数一次。但复杂度仍然是每种纸币枚举张数，对于 $n=10^3, w=10^4$ 不可行。

按编号顺序处理纸币这个约束，怎么在 DP 中体现？

设 $dp[j]$ 表示凑出金额 $j$ 的组合数。如果先枚举纸币 $i$ ，再用它更新所有金额 $j$ ，那么当处理到纸币 $i$ 时， $dp$ 中的方案只包含前 $i-1$ 种纸币。加入纸币 $i$ 后， $dp[j]$ 从 $dp[j-a_i]$ 转移——这意味着纸币 $i$ 一定出现在"编号顺序的最后"，即编号较小的纸币先被决定、编号较大的后用。这样就排除了不同顺序的重复计数。

为什么正序枚举 $j$ ？

每种纸币无限张， $dp[j-a_i]$ 可能已经在本轮用同一种纸币更新过，所以正序可以让一种纸币被重复计入，符合"无限张"的要求。

这和纸币问题 2 的循环顺序有什么本质区别？

先枚举金额 $j$ ，再枚举纸币 $i$ ：最后一步可以是任意纸币， $dp[j-a_i]$ 中包含以任何纸币结尾的方案，不同顺序自然被认为是不同方案 → 排列
先枚举纸币 $i$ ，再枚举金额 $j$ ：纸币按编号顺序被依次使用，最后一步只能是当前或编号更小的纸币，不同顺序被合并 → 组合

DP 公式

设 $dp_j$ 表示凑出金额 $j$ 的纸币组合数。初始化 $dp_0 = 1$ ，其余 $dp_j = 0$ ：

dp_j = (dp_j + dp_{j-a_i}) \bmod (10^9+7) \qquad (j \geqslant a_i)

先枚举纸币 $i = 1 \dots n$ ，内层 $j = a_i \dots w$ 正序。最终答案为 $dp_w$ 。

样例 DP 表格

以样例 2 为例： $n=3, w=15$ ，面额 $1, 5, 11$ 。

处理纸币	面额	$dp[0]$	$dp[1]$	$dp[5]$	$dp[6]$	$dp[10]$	$dp[11]$	$dp[12]$	$dp[15]$
初始	—	1	0	0	0	0	0	0	0
纸币 1	1	1	1	1	1	1	1	1	1
纸币 2	5	1	1	$1+1=2$	$1+1=2$	$1+1=2$	$1+2=3$	$1+2=3$	$1+3=4$
纸币 3	11	1	1	2	2	2	$3+1=4$	$3+1=4$	$4+1=5$

答案 $dp[15] = 5$ 。五种组合： $(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)$ , $(5,5,5)$ , $(5,5,1,1,1,1,1)$ , $(5,1,1,1,1,1,1,1,1,1,1)$ , $(11,1,1,1,1)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXW = 10005;
const int MOD = 1000000007;

int n;                // 纸币种类数
int w;                // 要凑出的金额
int a[MAXN];          // 每种纸币的面额
int dp[MAXW];         // dp[j] = 凑出金额 j 的组合数（组合，不同顺序算同一种）

void read_input() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
}

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    // 先枚举纸币再枚举金额，这样不同顺序会被合并为同一种组合。
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= w; j++) {
            dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
        }
    }

    cout << dp[w] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(nw)$
空间复杂度： $O(w)$

总结

纸币问题 2 和 3 对比了完全背包计数中循环顺序的决定性作用：

	纸币问题 2（排列）	纸币问题 3（组合）
外层循环	金额 $j$	纸币 $i$
内层循环	纸币 $i$	金额 $j$ （正序）
首项	$dp[0]=1$	$dp[0]=1$
不同顺序	算不同方案	合并为一种

建议把这两题放在一起反复练习，直到能独立解释为什么交换循环顺序就改变了计数语义。

目录

题意

思路

DP 公式

样例 DP 表格

代码

复杂度

总结