c++0-1背包问题怎么理解

在前端开发内容学习中，c++0-1背包问题怎么理解？状态转移与代码示例是常见主题。很多人在阅读时会遇到概念分散、步骤不清和注意点难以归纳的问题。本文按照基础概念、操作流程和关键细节，对相关内容进行整理。

c++0-1背包问题是动态规划里的基础题型，核心在于每件物品只能选一次。本文从题意拆解、状态转移、代码写法到常见错误逐步说明，帮助你真正看懂并写出可运行的实现。

什么是0-1背包问题

0-1背包问题通常给出若干件物品，每件物品有重量和价值，同时给出背包容量。要求在不超过容量的前提下，让总价值尽量大，而且每件物品只能取0次或1次。

这类题的难点不在枚举所有选法，而在于如何把大问题拆成可重复利用的小问题。只要明确状态含义和转移方向，题目就会从组合搜索变成有规律的表格计算。

• 常见输入包括物品数量 n、背包容量 m、每件物品的重量 w[i] 和价值 v[i]。
• 题目关键限制是每件物品只能选一次，这正是它与完全背包的本质区别。

状态怎么设计才清晰

最常见的定义是 dp[i][j] 表示前 i 件物品里，在背包容量不超过 j 的条件下，能够得到的最大总价值。这样定义后，第 i 件物品只有选与不选两种决策。

如果当前容量 j 放不下第 i 件物品，那么答案只能继承前一个状态；如果放得下，就比较不选它和选它以后剩余容量的最优值谁更大。这个比较过程就是状态转移的核心。

• 状态转移可以理解为两种情况比较：放不下时直接继承上一行，放得下时在选与不选之间取较大值。
• 初始化时，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++完整代码示例

二维数组写法最适合理解过程，因为它把每一步选择都保留下来。初学时先把二维版本写对，再去做一维滚动优化，会更容易分清楚为什么循环方向必须倒着走。

下面这段示例直接读取输入，输出最大价值，适合用来验证状态定义和转移是否正确。

• 完整示例

  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  
  int main() {
      int n, m;
      cin >> n >> m;
  
      vector<int> w(n + 1), v(n + 1);
      for (int i = 1; i <= n; ++i) {
          cin >> w[i] >> v[i];
      }
  
      vector<vector<int>> dp(n + 1, vector<int>(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

样例输入输出怎么对应答案

把上面的代码代入同一组数据，就能看到它如何真正解题。输入里的第一行 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背包问题，重点不是死记公式，而是先看清状态表示什么、转移为什么成立。把二维版本写熟之后，再去做一维优化，动态规划这类题目会更容易形成稳定思路。