算法笔记:AcWing - 动态规划(背包问题)

算法笔记:AcWing - 动态规划(背包问题)

Ginkgo True love prevails.

写这篇的初衷:背包问题是 DP 的入门,但也是很多人的”劝退点”。状态转移方程背了就忘,一维优化搞不清正序倒序。这篇试着从”购物决策”的直觉出发,帮你理解每个方程背后的含义。

DP 的本质:把复杂问题拆成子问题,记住子问题的答案(状态),用子问题的答案拼出原问题的答案(转移)。


一、DP 的核心思维:状态设计 + 状态转移

先别急着看代码,想清楚两件事

1. 状态表示:f(i, j) 到底是什么意思?

背包问题里,f(i, j) 通常表示:

“只从前 i 个物品里选,且总体积不超过 j 的所有选法中,价值最大的那个方案的价值”

拆开看:

  • 集合:所有满足条件的选法
    • 条件 1:只从前 i 个物品里选
    • 条件 2:总体积 ≤ j
  • 属性:max(最大值)、min(最小值)、count(方案数)

2. 状态转移:f(i, j) 怎么从之前的状态算出来?

核心思想:集合划分。把”前 i 个物品选,体积≤j”这个集合,按”第 i 个物品选不选”划分成两个子集:

1
2
3
4
5
            f(i, j)
/ \
不选第 i 个 选第 i 个
↓ ↓
f(i-1, j) f(i-1, j-v[i]) + w[i]

转移方程:

1
f(i, j) = max(f(i-1, j), f(i-1, j-v[i]) + w[i])

为什么这样划分:因为第 i 个物品只有两种可能——选或不选。这样划分不重不漏,且两个子集都能用之前的状态表示。


二、01 背包:每个物品只能选一次

问题描述

有 n 个物品,背包容积为 V。每个物品有体积 v[i] 和价值 w[i]。每个物品最多选一次,求能装下的最大价值。

生活比喻:你去超市购物,购物车容量有限,每件商品只能买一件,怎么选让总价值最大?


二维写法(最直观)

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
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N]; // f[i][j]: 前 i 个物品,体积不超过 j 的最大价值

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];

// 枚举物品
for (int i = 1; i <= n; i++) {
// 枚举体积
for (int j = 0; j <= m; j++) {
// 不选第 i 个物品
f[i][j] = f[i-1][j];

// 选第 i 个物品(前提是装得下)
if (j >= v[i])
f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
}
}

cout << f[n][m] << endl;
}

图解转移过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
物品 1: 体积 2, 价值 3
物品 2: 体积 3, 价值 4
物品 3: 体积 4, 价值 5
背包容积:5

f[0][0~5] = 0 (还没选任何物品,价值都是 0)

选物品 1 后:
f[1][0] = 0, f[1][1] = 0, f[1][2] = 3, f[1][3] = 3, f[1][4] = 3, f[1][5] = 3

选物品 2 后:
f[2][0] = 0, f[2][1] = 0, f[2][2] = 3, f[2][3] = 4, f[2][4] = 5, f[2][5] = 7
(选物品 2) (选物品 2) (选 1+2) (选 1+2)

一维优化(滚动数组)

核心观察:f[i][j] 只依赖于 f[i-1][...],也就是说,算第 i 层时只需要第 i-1 层的数据。

优化思路:删掉第一维,用一维数组 f[j] 表示”体积不超过 j 的最大价值”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N]; // 一维优化

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];

for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) { // ⚠️ 注意:倒序枚举
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}

cout << f[m] << endl;
}

关键问题:为什么要倒序枚举?

这是 01 背包最容易混淆的地方。让我们对比一下:

二维转移方程:

1
f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i])

一维写法(删掉第一维):

1
f[j] = max(f[j], f[j - v[i]] + w[i])

问题:如果正序枚举(从小到大),会发生什么?

1
2
3
4
5
6
7
8
9
假设 v[1] = 2, w[1] = 3

正序枚举 j = 0, 1, 2, 3, 4, 5:

j=2: f[2] = max(f[2], f[0] + 3) = 3 ✓ 正确
j=3: f[3] = max(f[3], f[1] + 3) = 3 ✓ 正确
j=4: f[4] = max(f[4], f[2] + 3) = 6 ✗ 错误!物品 1 被用了两次!
↑
这里的 f[2] 是刚更新过的(已经选了物品 1),不是上一层的 f[2]

倒序枚举(从大到小):

1
2
3
4
5
6
倒序枚举 j = 5, 4, 3, 2, 1, 0:

j=5: f[5] = max(f[5], f[3] + 3) f[3] 还是上一层的值 ✓
j=4: f[4] = max(f[4], f[2] + 3) f[2] 还是上一层的值 ✓
j=3: f[3] = max(f[3], f[1] + 3) f[1] 还是上一层的值 ✓
j=2: f[2] = max(f[2], f[0] + 3) f[0] 还是上一层的值 ✓

结论:倒序枚举保证计算 f[j] 时,f[j - v[i]] 还是上一层的值,符合 01 背包”每个物品只能用一次”的要求。

记忆口诀:

01 背包要倒序,防止物品被复用


三、完全背包:每个物品可以选无限次

问题描述

和 01 背包一样,但每个物品可以选任意多次(只要装得下)。

生活比喻:超市里的散装糖果,可以随便抓,只要袋子装得下。


朴素思路(三重循环)

最直接的想法:枚举每个物品选多少个。

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k * v[i] <= j; k++) { // 枚举选 k 个
f[i][j] = max(f[i][j], f[i-1][j - k * v[i]] + k * w[i]);
}
}
}

问题:时间复杂度 ,太慢了!


优化思路:利用已经算过的结果

关键观察:

1
2
3
4
5
6
7
8
9
10
f[i][j] = max(f[i-1][j], 
f[i-1][j-v] + w,
f[i-1][j-2v] + 2w,
...,
f[i-1][j-kv] + kw)

f[i][j-v] = max(f[i-1][j-v],
f[i-1][j-2v] + w,
...,
f[i-1][j-kv] + (k-1)w)

对比两个式子,发现:

1
f[i][j] = max(f[i-1][j], f[i][j-v] + w)

直觉解释:

  • f[i][j-v] 已经算过”在体积 j-v 下,前 i 个物品的最优解”
  • 这个最优解里可能已经选了若干个物品 i
  • 现在体积变成 j,只需要在 f[i][j-v] 的基础上再多选一个物品 i 就行

二维优化写法

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j]; // 不选
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); // ⚠️ 注意:这里是 f[i],不是 f[i-1]
}
}

和 01 背包的区别:f[i][j - v[i]] vs f[i-1][j - v[i]]

  • 01 背包:不能选第 i 个,所以用 f[i-1]
  • 完全背包:可以再选一个第 i 个,所以用 f[i]

一维优化写法

1
2
3
4
5
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) { // ⚠️ 注意:正序枚举
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}

为什么这次要正序?

因为完全背包允许重复选,我们需要 f[j - v[i]] 是当前层已经更新过的值(可能已经选了若干个物品 i)。

1
2
3
4
5
6
7
8
假设 v[1] = 2, w[1] = 3

正序枚举 j = 0, 1, 2, 3, 4, 5:

j=2: f[2] = max(f[2], f[0] + 3) = 3 (选了 1 个物品 1)
j=3: f[3] = max(f[3], f[1] + 3) = 3 (选了 1 个物品 1)
j=4: f[4] = max(f[4], f[2] + 3) = 6 (选了 2 个物品 1) ✓ 正确!
j=5: f[5] = max(f[5], f[3] + 3) = 6 (选了 2 个物品 1) ✓ 正确!

结论:正序枚举让 f[j - v[i]] 是当前层的值,符合完全背包”可以重复选”的要求。

记忆口诀:

完全背包要正序,允许物品重复选


01 背包 vs 完全背包:一行代码的区别

1
2
3
4
5
6
7
// 01 背包
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);

// 完全背包
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);

就差了个枚举方向,但背后的逻辑完全不同。理解了这个,你就掌握了背包问题的核心。


四、多重背包:每个物品有数量限制

问题描述

每个物品 i 最多选 s[i] 次(不同物品的数量限制可能不同)。

生活比喻:超市限购,每人最多买 5 瓶牛奶。


朴素写法(三重循环)

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
f[i][j] = max(f[i][j], f[i-1][j - k * v[i]] + k * w[i]);
}
}
}

问题:如果 s[i] 很大(比如 1000),复杂度会很高。


二进制优化:把多重背包转成 01 背包

核心思想:把 s 个物品打包成若干组,每组看作一个”新物品”,然后用 01 背包解决。

打包策略:用二进制拆分

1
2
3
4
5
6
7
8
9
10
11
假设 s = 200

打包成:1, 2, 4, 8, 16, 32, 64, 73
↑ ↑
2 的幂次 剩下的部分

验证:1+2+4+8+16+32+64 = 127
200 - 127 = 73

为什么这样打包?因为 1, 2, 4, 8... 可以组合出 0~127 的任意数
再加上 73,可以组合出 0~200 的任意数

数学原理:

  • 1, 2, 4, …, 2^k 可以组合出 0 到 2^(k+1)-1 的任意整数
  • 剩下的部分 c = s - (2^(k+1) - 1) 保证 c < 2^(k+1)
  • 这样打包后,任意 0 到 s 的数量都能被表示

代码实现

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
const int N = 25000;  // 拆分后的物品总数
int n, m;
int v[N], w[N];
int f[N];

int main() {
cin >> n >> m;

int cnt = 0; // 拆分后的物品计数
for (int i = 1; i <= n; i++) {
int a, b, s; // 体积、价值、数量
cin >> a >> b >> s;

int k = 1;
while (k <= s) {
cnt++;
v[cnt] = a * k; // 打包后的体积
w[cnt] = b * k; // 打包后的价值
s -= k;
k *= 2;
}
if (s > 0) { // 剩下的部分
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

n = cnt; // 更新物品总数

// 转成 01 背包
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}

cout << f[m] << endl;
}

复杂度对比:

  • 朴素:
  • 二进制优化:

为什么不用完全背包的优化思路?因为 s[i] 有限制,不能无限选,所以 f[i][j-v] + w 的推导不成立(可能会超过数量限制)。


五、分组背包:每组最多选一个

问题描述

有 n 组物品,每组有若干个。每组最多选一个物品,求最大价值。

生活比喻:餐厅点菜,每类菜(主食、主菜、饮料)只能选一道。


状态设计

和之前一样,f[j] 表示”体积不超过 j 的最大价值”。

转移思路:对于第 i 组,枚举选组内的哪个物品(或者不选)。

1
2
3
4
5
6
f[j] = max(
f[j], // 不选第 i 组的任何物品
f[j - v[i][0]] + w[i][0], // 选第 i 组的第 0 个
f[j - v[i][1]] + w[i][1], // 选第 i 组的第 1 个
...
)

代码实现

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
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N]; // s[i]: 第 i 组的物品数量
int f[N];

int main() {
cin >> n >> m;

for (int i = 1; i <= n; i++) {
cin >> s[i]; // 第 i 组有 s[i] 个物品
for (int j = 0; j < s[i]; j++)
cin >> v[i][j] >> w[i][j];
}

for (int i = 1; i <= n; i++) { // 枚举组
for (int j = m; j >= 0; j--) { // 枚举体积(倒序)
for (int k = 0; k < s[i]; k++) { // 枚举组内物品
if (j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}

cout << f[m] << endl;
}

注意:

  1. 体积要倒序枚举:因为每组只能选一个,本质上还是 01 背包的逻辑
  2. 循环顺序:组 → 体积 → 组内物品(不能交换)

六、四种背包问题对比总结

类型 限制条件 枚举方向 转移方程
01 背包 每个物品选 0 或 1 次 体积倒序 f[j] = max(f[j], f[j-v] + w)
完全背包 每个物品选无限次 体积正序 f[j] = max(f[j], f[j-v] + w)
多重背包 每个物品选 ≤ s 次 体积倒序 + 二进制拆分 转成 01 背包
分组背包 每组选 0 或 1 个 体积倒序 f[j] = max(f[j], f[j-v[i][k]] + w[i][k])

七、背包问题的 DP 分析框架

遇到任何 DP 问题,按这个框架思考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. 状态表示
- f[i][j] 表示什么?
- 集合是什么?(所有满足某条件的方案)
- 属性是什么?(max / min / count)

2. 状态转移
- 如何划分子问题?(通常按"最后一个/第一个"的选择划分)
- 转移方程是什么?

3. 初始化
- 边界条件是什么?
- f[0][0] 等于多少?

4. 优化
- 能否滚动数组?
- 枚举顺序有什么要求?

八、易错点总结

  1. 01 背包倒序,完全背包正序 —— 最容易记混
  2. 多重背包二进制拆分 —— 别忘了最后剩下的部分
  3. 分组背包循环顺序 —— 组→体积→组内物品,不能乱
  4. 数组下标 —— 从 0 还是从 1 开始,要统一
  5. 初始化 —— 求最大值时初始化为 0 或 -∞,求方案数时初始化为 0 或 1

最后提醒:背包问题的核心不是背模板,而是理解状态设计和转移方程背后的逻辑。多画图、多模拟,比死记硬背有效得多。

下一篇整理线性 DP、区间 DP 等其他 DP 类型~

  • Title: 算法笔记:AcWing - 动态规划(背包问题)
  • Author: Ginkgo
  • Created at : 2026-04-11 14:30:00
  • Updated at : 2026-04-12 16:22:19
  • Link: https://g1nkgo7.github.io/2026/04/11/算法笔记-AcWing-动态规划(背包问题)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments