01背包问题
问题定义
01背包问题是一个经典的组合优化问题，通常描述如下：
有个容量为C的背包
有n件物品，第i件物品的重量为Wi,价值为Vi
每种物品只有一件，可以选择放入背包（1）或不放入背包（0），因此称为“01”背包。
目标：在不超过背包容量的前提下，使装入背包的物品总价值最大。
2.动态规划解法
这是最常用的解法，核心是状态定义与状态转移方程。
（1）状态定义
设 dp[i][j]表示：考虑前 件物品，在背包容量为 时能获得的最大价值。
的范围：
的范围：
（2）状态转移
对于第 i 件物品（体积 v[i]，价值 w[i]）：
不选：
dp[i][j] = dp[i-1][j]选（前提是
j >= v[i]）：dp[i][j] = dp[i-1][j - v[i]] + w[i]
取两者最大值：
dp[i][j]=max(dp[i−1][j], dp[i−1][j−v[i]]+w[i])
（3）初始化
dp[0][j] = 0（没有物品可选时，价值为 0）dp[i][0] = 0（背包容量为 0 时，无法装任何物品）
（4）参考代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N, V;
cin >> N >> V;
int v[1005], w[1005];
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
// dp[i][j] 表示前 i 件物品，容量 j 的最大价值
int dp[1005][1005] = {0};
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) { // 从 0 开始更规范
if (j < v[i]) {
// 容量不够，只能不选
dp[i][j] = dp[i - 1][j];
} else {
// 容量足够，取“不选”和“选”的最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout << dp[N][V] << endl;
return 0;
}（5）例子详解
如果输入
4 5 1 2 2 4 3 4 4 5
| 物品编号 | 体积 v[i] | 价值 w[i] |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 4 |
| 3 | 3 | 4 |
| 4 | 4 | 5 |
背包容量： V = 5
开始逐步计算dp表
初始状态（i=0）：
容量 j: 0 1 2 3 4 5 dp[0]: 0 0 0 0 0 0
i=1（考虑第1件物品：体积1，价值2）
j=1: max(dp[0][1]=0, dp[0][0]+2=2) = 2 j=2: max(dp[0][2]=0, dp[0][1]+2=2) = 2 j=3: max(dp[0][3]=0, dp[0][2]+2=2) = 2 j=4: max(dp[0][4]=0, dp[0][3]+2=2) = 2 j=5: max(dp[0][5]=0, dp[0][4]+2=2) = 2 dp[1]: 0 2 2 2 2 2
i=2（考虑第2件物品：体积2，价值4）
j=1: dp[1][1]=2 (容量不够选物品2) j=2: max(dp[1][2]=2, dp[1][0]+4=4) = 4 j=3: max(dp[1][3]=2, dp[1][1]+4=6) = 6 j=4: max(dp[1][4]=2, dp[1][2]+4=6) = 6 j=5: max(dp[1][5]=2, dp[1][3]+4=6) = 6 dp[2]: 0 2 4 6 6 6
i=3（考虑第3件物品：体积3，价值4）
j=1: dp[2][1]=2 (容量不够) j=2: dp[2][2]=4 (容量不够) j=3: max(dp[2][3]=6, dp[2][0]+4=4) = 6 j=4: max(dp[2][4]=6, dp[2][1]+4=6) = 6 j=5: max(dp[2][5]=6, dp[2][2]+4=8) = 8 dp[3]: 0 2 4 6 6 8
i=4（考虑第4件物品：体积4，价值5）
j=1: dp[3][1]=2 (容量不够) j=2: dp[3][2]=4 (容量不够) j=3: dp[3][3]=6 (容量不够) j=4: max(dp[3][4]=6, dp[3][0]+5=5) = 6 j=5: max(dp[3][5]=8, dp[3][1]+5=7) = 8 dp[4]: 0 2 4 6 6 8
最终结果：
最大价值： dp[4][5] = 8
最优方案： 选择物品2（体积2，价值4）和物品3（体积3，价值4），总价值8，刚好用完容量5。
完整的dp表
| i\j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 2 | 4 | 6 | 6 | 6 |
| 3 | 0 | 2 | 4 | 6 | 6 | 8 |
| 4 | 0 | 2 | 4 | 6 | 6 | 8 |
关键点：
dp[i][j] = dp[i-1][j]：不选当前物品，继承前i-1件物品的最优解
dp[i-1][j-v[i]] + w[i]：选当前物品，用剩余容量 j-v[i] 在前i-1件物品中找最优解，加上当前物品价值
max(...)：在"选"和"不选"中选择价值更大的方案
3.一维数组优化
观察状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
发现 dp[i] 只依赖于 dp[i-1]，所以可以只用一维数组，倒序遍历容量，避免覆盖上一层的状态
一维 dp 定义：
dp[j] 表示容量为 j 的背包能装的最大价值。
状态转移：
dp[j]=max(dp[j], dp[j−v[i]]+w[i])
注意：j 从 V 到 v[i] 倒序遍历。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, V;
cin >> N >> V;
vector<int> v(N + 1), w(N + 1);
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
vector<int> dp(V + 1, 0);
for (int i = 1; i <= N; i++) {
// 必须倒序遍历，防止重复选择
for (int j = V; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
