小 A 点菜

题意

有 N 种菜，每种菜只有一份，价格为 a_i。手里有 M 元，问有多少种选菜方案，使总价格恰好等于 M。

思路

先看最直接的暴力：

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
44
45
46
47
48
49
50// brute.cpp：小数据暴力解，使用 01 序列枚举每种菜点或不点。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;              // 菜品种类数
int money;          // 需要恰好花掉的钱
int a[MAXN];        // 每种菜的价格
int choose_dish[MAXN]; // choose_dish[i] = 0/1，表示第 i 种菜不点/点
int answer_count;   // 当前方案数

int calc_money() {
    int sum_money = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_dish[i] == 1) sum_money += a[i];
    }
    return sum_money;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (calc_money() == money) {
            answer_count++;
        }
        return;
    }

    // 第 dep 种菜的 01 选择：0 不点，1 点。
    for (int i = 0; i <= 1; i++) {
        choose_dish[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

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

    answer_count = 0;
    dfs_choose(1);

    cout << answer_count << '\n';
    return 0;
}

brute.cpp 用 01 序列枚举每种菜点或不点，叶子节点检查总价是否恰好等于 $M$ ，并累计方案数。这个做法正确但复杂度 $O(2^N)$ ， $N=100$ 时不可行。

一句话本质： 01 背包的计数版本——dp[0]=1，dp[j] += dp[j-price]，倒序保证每道菜只选一次。

和求最大价值的 01 背包比，计数版本需要改什么？

求最大值用的是 max，计数用的是加法。 $dp[j]$ 的含义从"容量不超过 $j$ 的最大价值"变成"恰好花掉 $j$ 元的方案数"。

怎么保证"恰好"而不是"不超过"？

初始化只有 $dp[0]=1$ （花 0 元有一种方案：什么都不点），其余 $dp[j]=0$ 。转移时 $dp[j]$ 只从 $dp[j-price]$ 累加，只有那些能恰好凑出 $j$ 的路径才会对 $dp[j]$ 有贡献。达不到的金额始终为 0。

为什么倒序？

每道菜只有一份。倒序保证 $dp[j-price]$ 是处理前 $i-1$ 道菜的值（不含当前菜），防止同一道菜被多次计数。

这是 0/1 背包的计数版本。

设 dp[money] 表示已经处理过若干道菜后，恰好花掉 money 元的方案数。

初始化：

text

1dp[0] = 1

表示什么都不点时，花 0 元有一种方案。

处理价格为 price 的菜时，如果点这道菜，那么所有原本恰好花 money - price 元的方案，都能扩展成恰好花 money 元的方案：

text

1dp[money] += dp[money - price]

因为每道菜只能点一次，所以 money 必须倒序枚举。

样例 DP 表格

样例价格为 1,1,2,2，目标 4：

处理菜品	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]
初始	1	0	0	0	0
1	1	1	0	0	0
1	1	2	1	0	0
2	1	2	2	2	1
2	1	2	3	4	3

答案为 dp[4] = 3。

Python 知识

dp = [0] * (target + 1) 创建一维背包数组。
range(target, price - 1, -1) 是倒序枚举金额，保证每道菜只用一次。
Python 整数能直接保存答案；题目也保证答案不超过 32 位整数。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9
10
11n, target = map(int, input().split())
prices = list(map(int, input().split()))

dp = [0] * (target + 1)
dp[0] = 1

for price in prices:
    for money in range(target, price - 1, -1):
        dp[money] += dp[money - price]

print(dp[target])

C++ 解法

用 f[0] = 1 初始化，f[j] += f[j-w[i]] 倒序转移，统计恰好花完 M 元的方案数，和 Python 版思路完全一致：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2024-07-13 11:10
 * update_at: 2026-09-06 20:40
 */
//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2024-07-13 11:10:15
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
int w[maxn];
int f[10005];

int main (int argc, char *argv[]) {
    std::cin >> n >> m;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cin >> w[i];
    }
    f[0] = 1;

    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j =m ;j>=w[i];j--)
        {
            f[j] += f[j-w[i]];
        }
    }
    std::cout << f[m] << "\n";

    return 0;
}

复杂度

时间复杂度为 $O(NM)$ ，空间复杂度为 $O(M)$ 。

总结

看到“每个物品最多选一次，恰好凑出某个和，问方案数”，就可以往计数 0/1 背包上想。

一图流解析

保留已有一图流图片，作为读完正文后的复盘。

目录

题意

思路

样例 DP 表格

Python 知识

代码

C++ 解法

复杂度

总结

一图流解析