C++ 0-1背包问题是动态规划中的经典基础题，核心特点是每件物品只能选择一次。本文将从题目理解、状态设计、状态转移方程、C++代码实现到常见错误逐步讲清，帮助你真正看懂0-1背包算法，并写出正确可运行的程序。
什么是0-1背包问题
0-1背包问题通常会给出若干件物品，每件物品都有对应的重量和价值，同时还会给出一个背包容量。题目要求是在总重量不超过背包容量的前提下，使物品总价值尽可能大，并且每件物品只能选择0次或1次。
这类动态规划题的关键并不是暴力枚举所有选法，而是学会把原问题拆分为可以重复利用的子问题。只要把状态含义和转移方向理清楚，原本复杂的组合问题就能转化为有规律的动态规划表格计算。
- 常见输入包括物品数量 n、背包容量 m、每件物品的重量 w[i] 和价值 v[i]。
- 题目的核心限制是每件物品只能选一次，这也是0-1背包和完全背包之间最本质的区别。
状态怎么设计才清晰
最常见也最容易理解的定义是：dp[i][j] 表示在前 i 件物品中选择，且背包容量不超过 j 的条件下，能够获得的最大总价值。这样定义后，第 i 件物品只有“选”与“不选”两种决策。
如果当前容量 j 无法放下第 i 件物品，那么当前答案只能直接继承前一个状态；如果能够放下，就要比较“不选当前物品”和“选择当前物品后剩余容量的最优值”哪个更大。这个比较过程，就是0-1背包状态转移的核心逻辑。
- 状态转移可以理解为两种情况比较：放不下时直接继承上一行，放得下时在选与不选之间取最大值。
- 初始化时，
dp[0][j]一般都设为 0，表示没有任何物品可选时，总价值自然为 0。 - 先手算两三件物品的小样例，再对照状态表检查，通常最容易发现状态转移是否写正确。
用小样例真正看懂状态转移
如果只是死记公式，很多初学者在做题时往往不知道某个状态究竟是怎么推出来的。可以先看一个只有 3 件物品的小样例：背包容量 m=4，物品 1 的重量和价值为 (1, 15)，物品 2 为 (3, 20)，物品 3 为 (4, 30)。
先看 dp[1][4]。因为容量 4 可以放下第 1 件物品，所以要比较不选它时的 dp[0][4]=0，以及选它之后的 dp[0][3]+15=15，最终得到 dp[1][4]=15。
再看 dp[2][4]，这时需要比较 dp[1][4]=15 和 dp[1][1]+20=35，因此 dp[2][4]=35，说明同时选择第 1 件和第 2 件物品更优。
最后看 dp[3][4]，需要比较 dp[2][4]=35 和 dp[2][0]+30=30，所以 dp[3][4]=35，说明当容量为 4 时，前两件物品的组合依旧是最优解。
- 在这个过程中，
dp[i-1][j]表示不选当前物品，dp[i-1][j-w[i]]+v[i]表示选择当前物品后的总价值。 - 只要把某个状态代入具体数字，“选”还是“不选”哪个更优就会立刻变得非常直观。
样例状态表
容量 j: 0 1 2 3 4 dp[0][j]: 0 0 0 0 0 dp[1][j]: 0 15 15 15 15 dp[2][j]: 0 15 15 20 35 dp[3][j]: 0 15 15 20 35
C++完整代码示例
二维数组写法最适合理解0-1背包的完整过程，因为它会把每一步的决策结果都保留下来。对于初学者来说，先把二维动态规划版本写对，再去做一维滚动数组优化，会更容易理解为什么容量循环必须倒序遍历。
下面这段 C++ 示例代码可以直接读取输入并输出最大价值，适合用来验证状态定义、状态转移方程以及程序实现是否正确。
完整示例
#include#include #include using namespace std; int main() { int n, m; cin >> n >> m; vector w(n + 1), v(n + 1); for (int i = 1; i <= n; ++i) { cin >> w[i] >> v[i]; } vector (m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) { dp[i][j] = dp[i - 1][j]; if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); } } } cout << dp[n][m] << endl; return 0; } - 编译命令：
g++ -std=c++17 -O2 knapsack.cpp -o knapsack - 运行命令：
./knapsack
样例输入输出怎么对应答案
把上面的 C++ 代码代入同一组测试数据，就能直观看到程序是如何求解0-1背包问题的。输入中的第一行 3 4 表示共有 3 件物品，背包容量为 4；后面三行则分别表示每件物品的重量和价值。
程序最终输出 35，因为当容量为 4 时，最优方案并不是只选重量 4、价值 30 的第 3 件物品，而是选择重量 1、价值 15 的第 1 件，再选择重量 3、价值 20 的第 2 件。这样总重量正好为 4，总价值达到 35。通过这个例子，题目条件、状态转移和程序输出之间的对应关系就完全串联起来了。
样例输入
3 4 1 15 3 20 4 30样例输出
35- 如果你手算出的最优值和程序输出不一致，通常应优先检查状态定义、数组下标范围以及状态转移条件是否写错。
一维优化和常见易错点
当你已经理解二维写法之后，就可以把二维状态压缩为一维数组来优化空间复杂度。但在一维优化中最容易出错的地方，就是容量必须从大到小遍历；否则同一件物品会在同一轮更新中被重复使用，结果就会错误地变成完全背包。
在实际做题时，还要特别注意数组下标、输入顺序以及初始化边界条件。有些背包题并不只是要求最大价值，还可能要求输出具体选法、恰好装满背包，或者统计方案数，这些都需要在原有动态规划状态定义的基础上继续细化。
- 一维优化的关键不只是少开一维数组，更重要的是保证每件物品在同一轮中只参与一次更新。
- 如果容量循环写成从小到大，当前物品就会被重复利用，最终求出的结果也就不再是标准的0-1背包答案。
- 调试程序时，可以先用很小的数据手工推导结果，再对照程序输出逐步检查每一步是否符合预期。
掌握0-1背包问题，重点不是机械背公式，而是先弄清楚状态表示的含义，以及状态转移为什么成立。把二维版本练熟之后，再继续做一维优化，你在学习动态规划和解决背包问题时就会更容易形成稳定、清晰的解题思路。
