动态规划系统课程 · 第三讲：背包 DP¶
本讲目标： 从“暴力枚举”出发，彻底理解背包问题为什么可以使用动态规划，并掌握 01 背包 → 完全背包 → 多重背包 → 分组背包 → 背包计数。
这一讲非常重要。对于中学生信息学竞赛来说，背包 DP 是必须熟练掌握的核心专题。
一、什么是背包问题？¶
先看一个生活中的问题。
你有一个容量为：
10 kg
的背包。
现在有若干物品：
| 物品 | 重量 | 价值 |
|---|---|---|
| 1 | 2 | 6 |
| 2 | 2 | 3 |
| 3 | 6 | 5 |
| 4 | 5 | 4 |
每件物品最多选择一次。
问题：
怎样选择物品，使总重量不超过 10 kg，并且总价值最大？
这就是最经典的：
01 背包问题¶
二、为什么叫“01 背包”？¶
因为对于每件物品：
0：不选
1：选
只有两个选择。
例如有 3 件物品：
物品1：0 / 1
物品2：0 / 1
物品3：0 / 1
总共有：
$$
2^3=8
$$
种选择。
如果有 n 件物品：
$$
2^n
$$
种选择。
三、最直接的暴力方法¶
假设：
n = 3
可以枚举：
000
001
010
011
100
101
110
111
例如：
011
表示：
不选物品1
选择物品2
选择物品3
这种方法的时间复杂度：
$$
O(2^n)
$$
当：
n = 10
还可以。
但是：
n = 50
就已经非常困难了。
因为：
$$
2^{50}\approx 1.12\times10^{15}
$$
显然不能直接枚举。
四、动态规划如何解决？¶
我们观察：
很多不同的选择方案，会产生相同的“当前状态”。
例如：
已经考虑前 i 件物品
背包剩余容量为 j
后面的决策只与这个状态有关，而不需要知道我们是通过什么具体方式到达这个状态的。
这就是动态规划能够发挥作用的地方。
五、01 背包：二维 DP¶
先不要急着优化成一维。
定义：
$$
dp[i][j]
$$
表示：
只考虑前 i 件物品，背包容量不超过 j 时能够获得的最大价值。
这个状态定义非常重要。
六、01 背包的状态转移¶
考虑第 i 件物品。
它有两种情况。
情况 1：不选第 i 件物品¶
那么：
$$
dp[i][j]=dp[i-1][j]
$$
因为没有选择第 i 件，所以答案与前 i-1 件物品一样。
情况 2：选择第 i 件物品¶
如果选择它，那么必须满足：
$$
w_i\le j
$$
剩余容量：
$$
j-w_i
$$
前面最多可以获得：
$$
dp[i-1][j-w_i]
$$
再加上当前物品的价值：
$$
v_i
$$
所以：
$$
dp[i][j]
=
dp[i-1][j-w_i]+v_i
$$
七、完整转移方程¶
因此：
$$
dp[i][j]
=
\begin{cases}
dp[i-1][j], & j<w_i\
\max(dp[i-1][j],dp[i-1][j-w_i]+v_i), & j\ge w_i
\end{cases}
$$
这就是最经典的：
01 背包状态转移方程¶
八、第一道题：经典 01 背包¶
题目¶
有 n 件物品和一个容量为 W 的背包。
第 i 件物品：
重量：w[i]
价值：v[i]
每件物品最多选择一次。
求最大价值。
输入¶
4 10
2 6
2 3
6 5
5 4
分析¶
物品：
物品1：重量2，价值6
物品2：重量2，价值3
物品3：重量6，价值5
物品4：重量5，价值4
最优选择：
物品1 + 物品3
总重量：
$$
2+6=8
$$
总价值：
$$
6+5=11
$$
所以答案：
11
九、二维 DP C++ 实现¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n + 1);
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
vector<vector<int>> dp(
n + 1,
vector<int>(W + 1, 0)
);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
// 不选第 i 件物品
dp[i][j] = dp[i - 1][j];
// 选择第 i 件物品
if (j >= w[i]) {
dp[i][j] = max(
dp[i][j],
dp[i - 1][j - w[i]] + v[i]
);
}
}
}
cout << dp[n][W] << '\n';
return 0;
}
十、为什么可以优化成一维？¶
观察二维转移：
$$
dp[i][j]
$$
实际上只依赖：
$$
dp[i-1][j]
$$
和：
$$
dp[i-1][j-w_i]
$$
也就是说：
当前第
i层只需要上一层的数据。
因此理论上没有必要保存整个二维数组。
可以压缩成：
dp[j]
表示：
当前已经处理的物品，在容量不超过
j时的最大价值。
于是：
$$
dp[j]
=
\max(dp[j],dp[j-w_i]+v_i)
$$
但是这里出现了一个非常关键的问题：
循环应该从哪里开始？¶
十一、为什么 01 背包必须倒序？¶
代码：
for (int j = W; j >= w[i]; j--)
为什么？
假设当前物品：
重量 = 2
价值 = 3
容量：
W = 6
如果我们正序：
j = 2
j = 3
j = 4
j = 5
j = 6
那么：
dp[2]
可能已经使用了当前物品。
当计算：
dp[4]
时：
dp[4] = dp[2] + 3
这里的 dp[2] 已经包含当前物品。
于是相当于：
当前物品 + 当前物品
也就是：
同一件物品被使用了两次。
这就不是 01 背包了。
十二、倒序为什么可以避免重复？¶
如果：
for (int j = W; j >= w[i]; j--)
那么计算：
dp[j]
时：
dp[j-w[i]]
还没有被当前物品更新。
它仍然代表：
只使用前
i-1件物品的结果。
所以：
dp[j-w[i]] + v[i]
恰好表示：
在前
i-1件物品的基础上，再选择第i件。
这保证了当前物品最多使用一次。
十三、01 背包的一维代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
int w, v;
cin >> w >> v;
for (int j = W; j >= w; j--) {
dp[j] = max(
dp[j],
dp[j - w] + v
);
}
}
cout << dp[W] << '\n';
return 0;
}
十四、学生必须真正理解的一句话¶
以后看到：
for (int j = W; j >= w; j--)
不要只记：
“01 背包就是倒序。”
而要理解：
倒序是为了让当前物品不能使用自己刚刚更新出来的状态。
这才是背包 DP 的本质。
十五、第二道题：完全背包¶
现在改变一个条件。
每种物品可以无限次使用。
例如：
物品1：重量2，价值3
那么可以：
选择 0 件
选择 1 件
选择 2 件
选择 3 件
...
这就是：
完全背包¶
十六、完全背包状态¶
仍然定义：
$$
dp[j]
$$
表示：
容量不超过
j时的最大价值。
转移仍然是：
$$
dp[j]
=
\max(dp[j],dp[j-w_i]+v_i)
$$
但是：
循环方向改变了！¶
完全背包：
for (int j = w[i]; j <= W; j++)
也就是：
从小到大。
十七、为什么完全背包必须正序？¶
还是：
重量 = 2
价值 = 3
容量：
W = 6
正序：
j = 2
得到：
dp[2] = 3
然后：
j = 4
可以使用刚刚更新的：
dp[2]
于是：
dp[4] = dp[2] + 3
= 6
这正好表示：
选择两件物品
继续：
dp[6] = dp[4] + 3
= 9
表示：
选择三件物品
因此：
正序更新，恰好允许当前物品重复使用。
十八、01 背包与完全背包对比¶
| 01 背包 | 完全背包 | |
|---|---|---|
| 每件物品 | 最多一次 | 无限次 |
| 转移 | dp[j-w]+v |
dp[j-w]+v |
| 循环方向 | 从大到小 | 从小到大 |
| 核心原因 | 防止重复使用 | 允许重复使用 |
记忆口诀：
01 倒序，完全正序。
但真正理解：
倒序 = 不允许使用当前层刚更新的数据。
正序 = 允许使用当前层刚更新的数据。
十九、第二道题：完全背包 C++ 实现¶
题目¶
有 n 种物品，每种物品可以无限次选择。
求容量不超过 W 时的最大价值。
C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
int w, v;
cin >> w >> v;
for (int j = w; j <= W; j++) {
dp[j] = max(
dp[j],
dp[j - w] + v
);
}
}
cout << dp[W] << '\n';
return 0;
}
二十、第三道题：多重背包¶
现在继续改变条件。
每种物品不能无限使用，但是有数量限制。
例如：
物品1：
重量 = 2
价值 = 3
数量 = 4
那么可以选择：
0 件
1 件
2 件
3 件
4 件
这就是：
多重背包¶
二十一、最直接的多重背包 DP¶
定义：
dp[j]
仍然表示：
容量不超过
j时的最大价值。
对于物品：
重量 w
价值 v
数量 c
我们枚举使用多少件：
$$
k=0,1,2,\ldots,c
$$
如果选择 k 件：
总重量：
$$
k\times w
$$
总价值：
$$
k\times v
$$
因此：
$$
dp[j]
=
\max_{0\le k\le c}
{dp[j-k w]+kv}
$$
二十二、多重背包的朴素实现¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
int w, v, c;
cin >> w >> v >> c;
for (int j = W; j >= w; j--) {
for (int k = 1;
k <= c && k * w <= j;
k++) {
dp[j] = max(
dp[j],
dp[j - k * w] + k * v
);
}
}
}
cout << dp[W] << '\n';
return 0;
}
二十三、这个算法有什么问题？¶
假设：
W = 100000
c = 100000
那么：
j
循环一次。
内部还有：
k
循环。
复杂度可能达到：
$$
O(nWc)
$$
非常慢。
所以我们需要优化。
二十四、多重背包优化：二进制拆分¶
这是竞赛中必须掌握的技巧。
假设：
c = 13
我们不需要把 13 件物品一个一个处理。
可以拆成：
1
2
4
6
因为：
$$
1+2+4+6=13
$$
于是原来的：
13 件相同物品
变成：
4 个 01 背包物品
它们分别表示：
1 件
2 件
4 件
6 件
二十五、为什么二进制拆分可以表示 0～13？¶
使用：
1
2
4
6
可以组合出：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
例如：
9 = 1 + 2 + 6
11 = 1 + 4 + 6
13 = 1 + 2 + 4 + 6
因此可以覆盖所有可能的选择数量。
二十六、二进制拆分后的物品¶
原始物品：
重量 = w
价值 = v
数量 = c
拆成若干个新的 01 物品。
例如：
数量 1：
重量 = w
价值 = v
数量 2：
重量 = 2w
价值 = 2v
数量 4：
重量 = 4w
价值 = 4v
剩余部分：
重量 = 6w
价值 = 6v
然后直接使用：
01 背包¶
因为每个拆出来的“组”最多使用一次。
二十七、多重背包二进制优化 C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<pair<int, int>> items;
for (int i = 1; i <= n; i++) {
int w, v, c;
cin >> w >> v >> c;
int k = 1;
while (c > 0) {
int take = min(k, c);
items.push_back({
w * take,
v * take
});
c -= take;
k *= 2;
}
}
vector<int> dp(W + 1, 0);
// 转化后的物品全部按照 01 背包处理
for (auto [w, v] : items) {
for (int j = W; j >= w; j--) {
dp[j] = max(
dp[j],
dp[j - w] + v
);
}
}
cout << dp[W] << '\n';
return 0;
}
二十八、三种背包终于可以统一理解了¶
现在把三种背包放到一起。
01 背包¶
每件物品：
0 或 1 次
for (j = W; j >= w; j--)
完全背包¶
每件物品：
0、1、2、3、... 次
for (j = w; j <= W; j++)
多重背包¶
每件物品：
0 ~ c 次
可以：
枚举数量
或者：
二进制拆分
二十九、第四道题：分组背包¶
继续增加一个限制。
假设有若干组物品：
第 1 组：
物品 A
物品 B
物品 C
第 2 组：
物品 D
物品 E
第 3 组：
物品 F
物品 G
要求：
每组最多选择一个物品。
这就是：
分组背包¶
三十、分组背包状态¶
定义：
$$
dp[j]
$$
表示：
处理完当前这些组以后，容量不超过
j时的最大价值。
处理某一组时：
枚举这一组选择哪个物品。
状态转移：
$$
dp[j]
=
\max(dp[j],dp[j-w]+v)
$$
但是必须保证：
不能在同一组中选择两个物品。
因此容量仍然需要：
从大到小
三十一、分组背包完整 C++ 代码¶
假设输入格式：
n W
每组：
k
w1 v1
w2 v2
...
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
for (int group = 1; group <= n; group++) {
int k;
cin >> k;
vector<pair<int, int>> items(k);
for (int i = 0; i < k; i++) {
cin >> items[i].first
>> items[i].second;
}
// 处理这一组
for (int j = W; j >= 0; j--) {
for (auto [w, v] : items) {
if (j >= w) {
dp[j] = max(
dp[j],
dp[j - w] + v
);
}
}
}
}
cout << dp[W] << '\n';
return 0;
}
三十二、为什么分组背包也要倒序？¶
因为一组里面：
只能选择一个。
如果正序更新，就可能发生：
选择本组物品 A
↓
使用刚刚更新的 dp
↓
再选择本组物品 B
最终：
同一组选择了两个物品。
所以必须倒序。
三十三、第五道题：背包方案数¶
前面的背包都是：
求最大价值。
但 DP 不仅可以求最大值。
还可以：
求方案数量。
例如：
有：
1 2 3
三种物品，每种最多选择一次。
问：
凑出容量
4有多少种选择方案？
可以选择：
1 + 3
或者：
1 + 2
所以有 2 种。
三十四、状态设计发生了变化¶
以前：
dp[j] = 最大价值
现在：
dp[j] = 凑出容量 j 的方案数
这就是非常重要的思想：
同样的状态维度，可以存储完全不同的东西。
三十五、01 背包求方案数¶
初始化：
dp[0] = 1;
为什么？
因为：
什么都不选，凑出 0，存在 1 种方案。
转移：
dp[j] += dp[j - w];
注意：
不是 max
而是：
+
因为我们在统计方案数量。
三十六、C++ 完整代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
// 什么都不选，凑出 0 有一种方案
dp[0] = 1;
for (int i = 1; i <= n; i++) {
int w;
cin >> w;
// 01 背包必须倒序
for (int j = W; j >= w; j--) {
dp[j] += dp[j - w];
}
}
cout << dp[W] << '\n';
return 0;
}
三十七、这里出现了一个非常重要的 DP 思想¶
请仔细比较：
求最大价值¶
dp[j] = max(
dp[j],
dp[j - w] + v
);
求方案数量¶
dp[j] += dp[j - w];
也就是说：
DP 的本质不是某个固定公式，而是“状态 + 状态之间的组合关系”。
不同的问题可能分别使用：
max
min
+
乘法
布尔 OR
布尔 AND
等等。
三十八、背包 DP 的统一模型¶
现在我们可以把很多背包问题统一起来。
设：
物品 i
重量：w[i]
价值：v[i]
核心状态：
dp[j]
然后根据“物品可以使用多少次”决定转移方式。
背包 DP
│
┌────────────┼────────────┐
│ │ │
01 完全 多重
│ │ │
最多1次 无限次 最多c次
│ │ │
倒序 正序 二进制拆分
三十九、背包 DP 最重要的判断题¶
以后看到题目，先不要写代码。
问：
问题 1¶
每个物品最多使用几次？
一次 → 01 背包
无限 → 完全背包
有限次 → 多重背包
问题 2¶
是每组最多选一个吗？
如果是：
分组背包
问题 3¶
求什么？
最大价值
最小费用
方案数量
是否可行
这会决定 DP 数组里保存什么。
四十、背包 DP 的“状态定义三原则”¶
以后设计背包 DP 时，可以使用这三个问题。
原则 1：容量是什么？¶
例如：
dp[j]
中的 j 通常表示：
当前背包容量。
原则 2：已经处理了什么？¶
二维 DP：
dp[i][j]
中：
i
通常表示：
已经考虑前 i 件物品。
原则 3：dp 中存的是什么？¶
可能是：
最大价值
最小费用
方案数
是否存在方案
所以不要看到：
dp[j]
就默认它一定是“最大价值”。
四十一、背包 DP 高频错误¶
错误 1：01 背包写成正序¶
错误：
for (int j = w; j <= W; j++)
这会允许物品重复使用。
错误 2：完全背包写成倒序¶
如果题目允许物品无限使用：
for (int j = W; j >= w; j--)
反而会限制物品最多使用一次。
错误 3：方案数初始化为 0¶
错误：
vector<long long> dp(W + 1, 0);
然后没有：
dp[0] = 1;
那么所有状态都可能一直是 0。
正确：
dp[0] = 1;
因为：
空集合是一种合法的初始方案。
错误 4：把“容量恰好为 j”和“不超过 j”混淆¶
例如：
dp[j]
可能表示：
容量不超过 j。
也可能表示：
恰好使用 j 的容量。
这两个定义不一样，初始化也可能不同。
一定要先明确。
四十二、一个非常重要的思维训练¶
假设：
W = 10
有一个物品：
w = 3
v = 5
问：
01 背包中，这个物品最多能贡献多少价值？¶
答案：
5
因为最多一次。
完全背包呢？¶
可以：
3 + 3 + 3
所以最大可以贡献：
15
多重背包，数量为 2？¶
最多：
3 + 3
价值：
10
这个例子非常适合帮助学生理解：
循环方向实际上是在控制“当前物品能不能再次进入状态”。
四十三、背包 DP 学习到这里，应该达到什么水平？¶
学生现在至少应该能够看到：
每件物品最多一次
马上想到：
for (j = W; j >= w; j--)
看到：
每件物品无限次
马上想到：
for (j = w; j <= W; j++)
看到：
每件物品最多 c 次
想到：
多重背包
然后根据数据范围决定：
朴素枚举
还是：
二进制拆分
四十四、今天的知识地图¶
背包 DP
│
┌──────────────┼──────────────┐
│ │ │
01背包 完全背包 多重背包
│ │ │
0/1次 无限次 0~c次
│ │ │
倒序 正序 二进制拆分
│ │ │
└──────────────┼──────────────┘
│
分组背包
│
每组最多一个
│
↓
背包方案计数
│
dp[j] 表示方案数
│
↓
更复杂背包
│
┌──────────────┼──────────────┐
│ │ │
二维费用 混合背包 树上背包
四十五、本讲必须掌握的 8 个结论¶
请让学生尝试脱离代码回答：
① 01 背包为什么叫 01？¶
因为每件物品只能：
0 次或 1 次
② 01 背包为什么倒序？¶
因为防止当前物品重复使用。
③ 完全背包为什么正序？¶
因为允许当前物品重复进入后续状态。
④ 多重背包是什么？¶
每件物品有数量上限。
⑤ 多重背包为什么可以二进制拆分？¶
因为若干个特殊数量的“组”可以组合出 0 ~ c 中的任意数量。
⑥ dp[0] = 1 在方案计数中是什么意思？¶
不选择任何物品，是凑出 0 的一种方案。
⑦ 背包 DP 的 dp[j] 一定代表最大价值吗？¶
不一定。
它可以表示：
最大价值
最小费用
方案数
是否可行
⑧ 学背包最重要的是什么？¶
不是背代码，而是：
弄清楚状态表示什么，以及当前物品是否可以使用已经更新过的状态。
四十六、课后训练题¶
建议按照以下顺序练习。
Level 1：必须独立完成¶
练习 1¶
容量 W，每件物品只能选择一次，求最大价值。
要求：
- 写出二维 DP。
- 再优化成一维 DP。
- 解释为什么倒序。
练习 2¶
每件物品可以无限选择，求最大价值。
要求：
- 写出状态定义。
- 写出转移方程。
- 解释为什么正序。
练习 3¶
每种物品有数量限制 c[i]。
要求：
- 先写朴素多重背包。
- 再使用二进制拆分。
- 比较两种算法复杂度。
四十七、Level 2：开始综合训练¶
完成：
01 背包求最大价值
01 背包求方案数
01 背包判断是否可行
完全背包求最大价值
完全背包求方案数
多重背包
分组背包
二维费用背包
这一阶段非常重要，因为学生会开始发现：
“背包”其实不是一道题，而是一整套状态设计模型。
四十八、下一阶段：区间 DP¶
下一讲我们进入：
第四讲：区间 DP¶
这是 DP 难度的一次明显提升。
重点学习：
dp[l][r]
为什么区间 DP 通常需要：
for (int len = 2; len <= n; len++)
以及如何从：
一个区间
拆成：
左区间 + 右区间
重点讲解三类经典问题：
- 石子合并
- 最长回文子序列
- 矩阵链乘法
并进一步学习：
- 区间 DP 的“最后一次操作”思想
- 为什么必须按照区间长度递增计算
- 前缀和如何优化区间求和
- 如何从区间 DP 推导更复杂的竞赛题
- 如何判断一道题是不是区间 DP
等学生掌握这些内容之后，再进入 树形 DP、DAG DP、状态压缩 DP、数位 DP，最后再学习 DP 优化。