算法笔记:AcWing - 动态规划(背包问题)
写这篇的初衷:背包问题是 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 | f(i, j) |
转移方程:
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 | const int N = 1010; |
图解转移过程:
1 | 物品 1: 体积 2, 价值 3 |
一维优化(滚动数组)
核心观察:f[i][j] 只依赖于 f[i-1][...],也就是说,算第 i 层时只需要第 i-1 层的数据。
优化思路:删掉第一维,用一维数组 f[j] 表示”体积不超过 j 的最大价值”。
1 | const int N = 1010; |
关键问题:为什么要倒序枚举?
这是 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 | 假设 v[1] = 2, w[1] = 3 |
倒序枚举(从大到小):
1 | 倒序枚举 j = 5, 4, 3, 2, 1, 0: |
结论:倒序枚举保证计算
f[j]时,f[j - v[i]]还是上一层的值,符合 01 背包”每个物品只能用一次”的要求。
记忆口诀:
01 背包要倒序,防止物品被复用
三、完全背包:每个物品可以选无限次
问题描述
和 01 背包一样,但每个物品可以选任意多次(只要装得下)。
生活比喻:超市里的散装糖果,可以随便抓,只要袋子装得下。
朴素思路(三重循环)
最直接的想法:枚举每个物品选多少个。
1 | for (int i = 1; i <= n; i++) { |
问题:时间复杂度
优化思路:利用已经算过的结果
关键观察:
1 | f[i][j] = max(f[i-1][j], |
对比两个式子,发现:
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 | for (int i = 1; i <= n; i++) { |
和 01 背包的区别:
f[i][j - v[i]]vsf[i-1][j - v[i]]
- 01 背包:不能选第 i 个,所以用
f[i-1]- 完全背包:可以再选一个第 i 个,所以用
f[i]
一维优化写法
1 | for (int i = 1; i <= n; i++) { |
为什么这次要正序?
因为完全背包允许重复选,我们需要 f[j - v[i]] 是当前层已经更新过的值(可能已经选了若干个物品 i)。
1 | 假设 v[1] = 2, w[1] = 3 |
结论:正序枚举让
f[j - v[i]]是当前层的值,符合完全背包”可以重复选”的要求。
记忆口诀:
完全背包要正序,允许物品重复选
01 背包 vs 完全背包:一行代码的区别
1 | // 01 背包 |
就差了个枚举方向,但背后的逻辑完全不同。理解了这个,你就掌握了背包问题的核心。
四、多重背包:每个物品有数量限制
问题描述
每个物品 i 最多选 s[i] 次(不同物品的数量限制可能不同)。
生活比喻:超市限购,每人最多买 5 瓶牛奶。
朴素写法(三重循环)
1 | for (int i = 1; i <= n; i++) { |
问题:如果 s[i] 很大(比如 1000),复杂度会很高。
二进制优化:把多重背包转成 01 背包
核心思想:把 s 个物品打包成若干组,每组看作一个”新物品”,然后用 01 背包解决。
打包策略:用二进制拆分
1 | 假设 s = 200 |
数学原理:
- 1, 2, 4, …, 2^k 可以组合出 0 到 2^(k+1)-1 的任意整数
- 剩下的部分
c = s - (2^(k+1) - 1)保证c < 2^(k+1) - 这样打包后,任意 0 到 s 的数量都能被表示
代码实现
1 | const int N = 25000; // 拆分后的物品总数 |
复杂度对比:
- 朴素:
- 二进制优化:
为什么不用完全背包的优化思路?因为
s[i]有限制,不能无限选,所以f[i][j-v] + w的推导不成立(可能会超过数量限制)。
五、分组背包:每组最多选一个
问题描述
有 n 组物品,每组有若干个。每组最多选一个物品,求最大价值。
生活比喻:餐厅点菜,每类菜(主食、主菜、饮料)只能选一道。
状态设计
和之前一样,f[j] 表示”体积不超过 j 的最大价值”。
转移思路:对于第 i 组,枚举选组内的哪个物品(或者不选)。
1 | f[j] = max( |
代码实现
1 | const int N = 110; |
注意:
- 体积要倒序枚举:因为每组只能选一个,本质上还是 01 背包的逻辑
- 循环顺序:组 → 体积 → 组内物品(不能交换)
六、四种背包问题对比总结
| 类型 | 限制条件 | 枚举方向 | 转移方程 |
|---|---|---|---|
| 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 | 1. 状态表示 |
八、易错点总结
- 01 背包倒序,完全背包正序 —— 最容易记混
- 多重背包二进制拆分 —— 别忘了最后剩下的部分
- 分组背包循环顺序 —— 组→体积→组内物品,不能乱
- 数组下标 —— 从 0 还是从 1 开始,要统一
- 初始化 —— 求最大值时初始化为 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.