背包问题（0-1背包）
较难38背包问题（0-1背包）—— 选或不选，做出最优决策
1. 问题引入：从“带零食去春游”说起
小明要去春游，他有一个容量为 5 公斤 的背包，想带一些零食。家里有 4 种零食：
| 零食 | 重量（公斤） | 喜爱程度（价值） |
|---|---|---|
| 薯片 | 2 | 3 |
| 巧克力 | 1 | 2 |
| 饼干 | 3 | 4 |
| 果冻 | 2 | 2 |
每种零食只有一包（不能拆开，也不能带半包）。小明想：在不超过背包总重量的前提下，怎样组合才能让总喜爱程度（价值）最高？
这就是经典的 0-1 背包问题：有 n 件物品，每件物品只能选择 0 次或 1 次（不能重复拿），背包容量为 m。第 i 件物品重量 w[i]，价值 v[i]。求在不超过容量的前提下，能获得的最大总价值。
输入示例：
n = 4, m = 5
物品1: w=2, v=3
物品2: w=1, v=2
物品3: w=3, v=4
物品4: w=2, v=2
输出： 最大价值 7（选薯片和饼干，总重2+3=5，价值3+4=7）。
（巧克力+果冻+薯片也行？总重1+2+2=5，价值2+2+3=7，同样得到7。所以可能存在多种最佳方案，但价值相同。）
2. 基本思路：二维动态规划（把大问题拆成小问题）
2.1 状态定义 —— 用表格记录“已经考虑了多少物品”
我们要解决的是：从所有物品中挑选，但直接思考很困难。动态规划的思路是 逐步考虑：先只看第一件物品，再看前两件……每考虑一件，就更新所有可能容量下的最佳价值。
定义 dp[i][j] 表示 考虑前 i 个物品（即物品1到物品i），在背包容量为 j 的情况下，能够获得的最大价值。
i从0到n，i=0表示还没有考虑任何物品（空手）。j从0到m，j=0表示背包容量为0（什么都装不了）。
这样，最终答案就是 dp[n][m]：考虑完所有物品，容量为 m 时的最大价值。
2.2 状态转移方程 —— 选还是不选？
对于第 i 个物品，我们只有两种选择：
- 不选：那么背包里的物品完全来自前
i-1个物品，容量不变，价值也不变：dp[i][j] = dp[i-1][j]。 - 选：前提是当前容量
j至少能装下这个物品（j >= w[i]）。如果选，那么背包要腾出w[i]的空间来放这个物品，剩下的容量j - w[i]用来装前i-1个物品的最优组合：dp[i][j] = dp[i-1][j - w[i]] + v[i]。
因为我们要最大价值，所以取两者中的较大值。
公式（简洁版）：
如果 j < w[i]： // 容量不够，只能不选
dp[i][j] = dp[i-1][j]
否则：
dp[i][j] = max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i] )
边界条件：
dp[0][j] = 0（没有物品时，任何容量价值都是0）dp[i][0] = 0（容量为0时，任何物品都放不下，价值也是0）
2.3 生活中的类比
想象你正在排队买奶茶，你手里有 5 元，前面有 4 种奶茶杯（每种只有一杯），每杯有价格和美味值。你只能选其中几杯，总价不超过 5 元。你可以这样思考：
- 先看第一杯（2元，美味3）：是拿还是不拿？
- 再看第二杯（1元，美味2）：在考虑了第一杯的基础上，再决定是否加这杯。
- ……
动态规划表格就是帮你记录“到目前为止，某个价格下最多能获得多少美味”。
3. 实例推演（填二维表格）
我们还是用春游零食的例子。构建一个 (n+1) × (m+1) 的表格，行 i 从0到4，列 j 从0到5。
初始状态（i=0行全0）：
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 |
3.1 填第1行（i=1，薯片：w=2, v=3）
- 容量0和1：装不下薯片，直接继承上一行的0 →
dp[1][0]=0, dp[1][1]=0 - 容量2：可以选薯片，比较不选（0）和选（dp[0][0]+3=3），取3 →
dp[1][2]=3 - 容量3：选薯片后剩余容量1，dp[0][1]=0，价值3；不选是0，取3 →
dp[1][3]=3 - 容量4、5同理：都是3
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | ||||||
| 3 | ||||||
| 4 |
3.2 填第2行（i=2，巧克力：w=1, v=2）
- 容量0：装不下，继承0 →
dp[2][0]=0 - 容量1：可以选巧克力，比较不选（0）和选（dp[1][0]+2=2），取2 →
dp[2][1]=2 - 容量2：不选（dp[1][2]=3） vs 选巧克力后剩余1（dp[1][1]+2=0+2=2），取3 →
dp[2][2]=3 - 容量3：不选3 vs 选后剩余2（dp[1][2]+2=3+2=5），取5 →
dp[2][3]=5（薯片+巧克力，价值3+2=5） - 容量4：不选3 vs 选后剩余3（dp[1][3]+2=3+2=5），取5
- 容量5：不选3 vs 选后剩余4（dp[1][4]+2=3+2=5），取5
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 2 | 3 | 5 | 5 | 5 |
| 3 | ||||||
| 4 |
3.3 填第3行（i=3，饼干：w=3, v=4）
- 容量0~2：装不下，直接继承上一行：0,2,3
- 容量3：不选（dp[2][3]=5） vs 选饼干后剩余0（dp[2][0]+4=4），取5 →
dp[3][3]=5 - 容量4：不选5 vs 选后剩余1（dp[2][1]+4=2+4=6），取6 →
dp[3][4]=6（巧克力+饼干，价值2+4=6） - 容量5：不选5 vs 选后剩余2（dp[2][2]+4=3+4=7），取7 →
dp[3][5]=7（薯片+饼干，价值3+4=7）
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 2 | 3 | 5 | 5 | 5 |
| 3 | 0 | 2 | 3 | 5 | 6 | 7 |
| 4 |
3.4 填第4行（i=4，果冻：w=2, v=2）
- 容量0~1：继承0和2
- 容量2：不选（dp[3][2]=3） vs 选果冻后剩余0（dp[3][0]+2=2），取3 →
dp[4][2]=3 - 容量3：不选5 vs 选后剩余1（dp[3][1]+2=2+2=4），取5
- 容量4：不选6 vs 选后剩余2（dp[3][2]+2=3+2=5），取6
- 容量5：不选7 vs 选后剩余3（dp[3][3]+2=5+2=7），取7
最终表格：
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 2 | 3 | 5 | 5 | 5 |
| 3 | 0 | 2 | 3 | 5 | 6 | 7 |
| 4 | 0 | 2 | 3 | 5 | 6 | 7 |
最终答案：dp[4][5] = 7，对应方案：薯片+饼干（或薯片+巧克力+果冻）。
4. 二维DP代码实现（C++）
下面是一个完整的 C++ 程序，读入物品数和容量，再读入每个物品的重量和价值，输出最大价值。
#include <iostream>
#include <algorithm> // 为了使用 max 函数
using namespace std;
const int MAXN = 100; // 物品最大数量
const int MAXM = 1000; // 背包最大容量
int dp[MAXN+1][MAXM+1]; // dp[i][j] 表示前i个物品，容量j的最大价值
int w[MAXN+1], v[MAXN+1]; // w[i]重量，v[i]价值
int main() {
int n, m;
cin >> n >> m; // 输入物品个数和背包容量
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> v[i]; // 输入每个物品的重量和价值
}
// 初始化：dp[0][*] 和 dp[*][0] 默认都是0，全局变量自动为0，不需要额外赋值
for (int i = 1; i <= n; ++i) { // 遍历每个物品
for (int j = 0; j <= m; ++j) { // 遍历所有可能的容量
if (j < w[i]) { // 容量不够，只能不选
dp[i][j] = dp[i-1][j];
} else {
// 不选 vs 选
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][m] << endl; // 输出最大价值
return 0;
}
运行示例： 输入：
4 5
2 3
1 2
3 4
2 2
输出：
7
5. 复杂度分析（二维）
- 时间复杂度：
O(n * m)，因为有一个外循环（n个物品）和内循环（m种容量）。 - 空间复杂度：
O(n * m)，用一个二维数组存储所有状态。
当 n 和 m 较大时（比如 n=1000, m=100000），二维数组会占用约 1000×100000×4字节 ≈ 400MB，可能超出内存限制。因此我们需要 一维优化。
6. 一维优化（空间优化 —— 滚动数组思想）
6.1 优化原理
观察状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
第 i 行的数据只依赖于第 i-1 行的数据。也就是说，我们不需要保留所有历史行，只需要 当前行和上一行。进一步，如果我们 倒序更新，就可以用同一个一维数组来覆盖旧数据，同时保证用到的 dp[j - w[i]] 还是上一轮的值。
关键点：
- 定义
dp[j]表示 当前已经处理完前 i 个物品后，容量为 j 的最大价值。 - 对于每个物品
i，我们需要保证在更新dp[j]时，dp[j - w[i]]还是没考虑当前物品的值（即上一轮的结果）。 - 如果正序遍历
j从w[i]到m，那么dp[j - w[i]]可能已经被当前物品更新过了（变成了dp[i][j - w[i]]），这样就会导致同一个物品被多次使用，变成 完全背包。所以必须 倒序遍历j从m到w[i]。
新转移方程（一维）：
for (int j = m; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
其中 dp[j] 初始全为0，表示没有物品时价值为0。
6.2 一维推导表格（用相同例子验证）
初始化 dp[0..5] = [0,0,0,0,0,0]
处理物品1（薯片，w=2, v=3）：
- j=5: dp[5] = max(0, dp[3]+3=0+3) = 3
- j=4: dp[4] = max(0, dp[2]+3=0+3) = 3
- j=3: dp[3] = max(0, dp[1]+3=0+3) = 3
- j=2: dp[2] = max(0, dp[0]+3=0+3) = 3
- j=1,0 不更新
结果：
dp = [0,0,3,3,3,3]（与二维第1行一致）
处理物品2（巧克力，w=1, v=2）：
- j=5: dp[5] = max(3, dp[4]+2=3+2=5) = 5
- j=4: dp[4] = max(3, dp[3]+2=3+2=5) = 5
- j=3: dp[3] = max(3, dp[2]+2=3+2=5) = 5
- j=2: dp[2] = max(3, dp[1]+2=0+2) = 3
- j=1: dp[1] = max(0, dp[0]+2=2) = 2
结果：
dp = [0,2,3,5,5,5]（与二维第2行一致）
处理物品3（饼干，w=3, v=4）：
- j=5: dp[5] = max(5, dp[2]+4=3+4=7) = 7
- j=4: dp[4] = max(5, dp[1]+4=2+4=6) = 6
- j=3: dp[3] = max(5, dp[0]+4=0+4) = 5
结果：
dp = [0,2,3,5,6,7]（与二维第3行一致）
处理物品4（果冻，w=2, v=2）：
- j=5: dp[5] = max(7, dp[3]+2=5+2=7) = 7
- j=4: dp[4] = max(6, dp[2]+2=3+2=5) = 6
- j=3: dp[3] = max(5, dp[1]+2=2+2=4) = 5
- j=2: dp[2] = max(3, dp[0]+2=0+2) = 3
结果：
dp = [0,2,3,5,6,7]（与二维第4行一致）
最终 dp[m] = 7。
7. 一维优化代码（C++）
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXM = 1000; // 背包最大容量
int dp[MAXM+1]; // 一维数组，dp[j]表示容量j的最大价值
int w[105], v[105]; // 物品重量和价值，假设物品数不超过100
int main() {
int n, m;
cin >> n >> m; // 输入物品个数和背包容量
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> v[i]; // 输入每个物品的重量和价值
}
// 初始化：dp[0..m]默认为0（全局变量）
for (int i = 1; i <= n; ++i) { // 遍历每个物品
for (int j = m; j >= w[i]; --j) { // 倒序遍历容量
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m] << endl; // 输出最大价值
return 0;
}
注意： 内层循环 j 从 m 到 w[i]，不能写反。如果写成 for (int j = w[i]; j <= m; ++j) 就变成了完全背包（每件物品可以拿无限次）。
8. 复杂度分析（一维优化后）
- 时间复杂度：
O(n * m)，与二维相同，但常数略小（少了一层 if 分支）。 - 空间复杂度：
O(m)，大幅降低，可以处理更大规模的数据。
9. 常见误区与总结
9.1 新手易犯的错误
-
一维数组内层正序遍历
错误代码：for (int j = w[i]; j <= m; ++j) { // 正序！ dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }后果：同一个物品会被多次放入，变成完全背包，结果偏大。
正确做法：一定要倒序：for (int j = m; j >= w[i]; --j)。 -
忘记处理容量不足的情况
二维代码中，如果j < w[i]需要直接继承。一维代码中，由于倒序且只从w[i]开始更新，容量小于w[i]的部分自动不变，所以不用特殊处理。但有时新手会在外面写一个if (j >= w[i])条件，也可以，但倒序循环天然保证了这一点。 -
数组下标越界
一维代码中dp[j - w[i]]当j = w[i]时，j - w[i] = 0，是合法的。但如果物品重量为0（实际中不可能），需要特殊处理。 -
初始化问题
全局变量自动初始化为0，所以dp[0]=0没问题。但在某些情况下（比如求最小值），需要初始化为INF。0-1背包求最大值，0初始化是正确的。
9.2 总结
- 0-1背包是动态规划中最经典的问题，核心思想就是 “选或不选”。
- 二维DP容易理解，适合初学；一维DP节省空间，是竞赛中的标准写法。
- 掌握状态定义、转移方程和遍历顺序后，可以轻松解决很多变种问题，比如：
- 求方案数：
dp[j] += dp[j - w[i]]（初始化dp[0]=1） - 求最小价值：
dp[j] = min(...)（初始化dp[0]=0，其他为 INF） - 恰好装满：初始化
dp[0]=0，其他为 -INF，最后判断dp[m]是否为 -INF。
- 求方案数：
10. 相关知识点指引
如果你已经掌握了 0-1 背包，接下来可以学习：
- 完全背包：每件物品可以取无限次。只需要把一维内层循环改为 正序 即可。
- 多重背包：每件物品有有限数量
c[i]。可以用二进制拆分或单调队列优化。 - 混合背包：三种背包混合在一起。
- 分组背包：物品分成若干组，每组最多选一个。
- 二维费用背包：每个物品有两种费用（比如重量和体积），背包有两个限制。
这些都是在 0-1 背包基础上扩展而来的，理解了核心的“状态转移”思想，就能举一反三。
延伸思考：如果物品数量较多但背包容量较小，或者价值范围较小而重量范围很大，可以考虑另一种 DP 方法：把价值作为维度，求最小重量。比如 dp[v] 表示达到价值 v 所需的最小重量。这叫做 “换维DP”，在处理某些题目时非常有用。
例题精讲
在0-1背包问题中，每个物品最多能被选择几次？
在用一维数组优化0-1背包问题时，内层循环对容量j的遍历顺序应该是？
在0-1背包问题中，贪心算法（按单位价值降序选择）一定能得到最优解。
以下代码是0-1背包问题的二维动态规划实现，请补全空缺处的代码。
int n, V;
int w[105], v[105];
int dp[105][1005];
int main() {
// 输入n和V，以及每个物品的重量w[i]和价值v[i]（下标从1开始）
for(int i = 0; i <= V; i++) dp[0][i] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= V; j++) {
if(j < w[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], ___);
}
}
// 输出dp[n][V]
return 0;
}以下代码是0-1背包问题的一维数组优化实现，请补全空缺处的代码。
int n, V;
int w[105], v[105];
int dp[1005];
int main() {
// 输入n和V，以及每个物品的重量w[i]和价值v[i]（下标从1开始）
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) {
for(int j = V; j >= w[i]; j--) {
dp[j] = max(dp[j], ___);
}
}
// 输出dp[V]
return 0;
}