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

作者：袖梨 2026-09-06

在前端开发内容学习中，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;
}