0-1背包问题：要么拿，要么不拿

你有一个背包，容量是 C，面前有 n 个物品，每个物品有自己的重量 w[i] 和价值 v[i]，每个物品要么拿（1），要么不拿（0），不能只拿一部分。这就是 0-1背包问题。这就像你去超市购物，购物车大小有限，要在众多商品中选出总价值最高的组合。

0-1背包问题是动态规划中最经典的问题之一。学会它，你就能解决很多类似的“选择”问题，比如春游时在有限背包里装零食、比赛时在有限时间内做最多分值的题目，等等。

生活比喻：搬新家

家里要搬新房子，大卡车只能装下500公斤的东西。你的家当里有沙发（100公斤，价值800元）、电视（50公斤，价值500元）、书架（150公斤，价值600元）……你希望在不超重的前提下，让总价值最大。你不可能把所有东西都搬走，所以必须权衡。每一个物品要么搬上车（1），要么留下（0），不能拆开。这就是典型的0-1背包模型。

另一个例子：小明去秋游，只能带一个容量为3升的书包。他有矿泉水（1升，值2分）、薯片（2升，值3分）、巧克力（1升，值1分）。他该怎么装才能让快乐总分最高？通过计算，他应该选矿泉水和薯片（总重3升，总分5分）。

动态规划的核心思路

1. 状态定义

我们用 dp[i][j] 表示“从前 i 个物品中选出一些，放入容量为 j 的背包，能获得的最大价值”。

注意：这里 i 从 1 到 n，j 从 0 到 C。dp[0][j] 表示没有物品时，任何容量的价值都是 0。

2. 转移方程

对于第 i 个物品（重量 w[i]，价值 v[i]），我们有两种选择：

不拿它：那么当前状态等于前 i-1 个物品在同样容量下的最优值，即 dp[i][j] = dp[i-1][j]。
拿它：前提是背包剩余容量至少能装下 w[i]，即 j >= w[i]。拿之后，价值变为前 i-1 个物品在容量 j-w[i] 时的最优值加上 v[i]，即 dp[i][j] = dp[i-1][j-w[i]] + v[i]。

我们取两者中的较大值：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])   （前提：j >= w[i]）

如果不满足 j >= w[i]，则只能选择不拿：dp[i][j] = dp[i-1][j]

3. 边界条件

dp[0][j] = 0（没有物品时价值为0） dp[i][0] = 0（容量为0时价值为0）

最终答案就是 dp[n][C]，即考虑所有物品、容量为 C 时的最大价值。

生活例子：春游选零食

小明春游背包容量为 5 升。零食如下：

物品	重量（升）	快乐值
薯片	2	3
可乐	1	2
饼干	3	4
果冻	2	2

我们按照动态规划填表：

dp[0][*] = 0
考虑薯片：容量 j=2~~5 时，可以拿，价值 3；容量 0~~1 拿不了。
考虑可乐：容量 j=1, 拿可乐价值2；容量 j=3, 可以同时拿薯片和可乐（2+1=3升），价值 3+2=5。
……

最终得到 dp[4][5] = 6，即最佳选择是薯片+可乐+饼干（2+1+3=6升？超重了！实际上需要检查容量限制。经过计算，最佳组合是薯片(2)+可乐(1)+果冻(2) = 5升，价值 3+2+2=7）。

（这里只是一个示意，实际表格请自行推导。）

二维数组代码实现

下面是用二维数组保存所有中间状态的实现，易于理解。

#include <iostream>
#include <algorithm>  // 使用 max 函数
using namespace std;

int main() {
    int n, C;
    cin >> n >> C;                     // 输入物品个数和背包容量
    
    int w[105], v[105];                // w: 重量, v: 价值
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];           // 每个物品的重量和价值
    }
    
    int dp[105][1005] = {0};           // dp[i][j] 前i个物品容量j的最大价值，初始化为0
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= C; j++) {
            // 先假定不拿第i个物品
            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][C] << endl;          // 输出最大价值
    return 0;
}

输入示例：

输出：

滚动数组优化：省下很多内存

观察二维数组的转移方程：dp[i][j] 只依赖上一行 dp[i-1][...] 的值。所以我们其实只需要保留一行的结果，每次更新时，用新值覆盖旧值。但是要注意：因为每个物品只能用一次，必须从大到小更新容量 j，否则会重复使用同一个物品（就像你可以拿同一个物品多次，那就不对了）。

为什么从大到小？
假如容量从 0 到 C 正向更新，当 j 较小时，dp[j-w[i]] 已经是这一轮更新过的值（相当于已经拿了当前物品），如果再拿一次，就变成了无限背包。而从大到小更新，dp[j-w[i]] 还是上一轮（即还没有考虑当前物品）的值，所以每个物品只被考虑了一次。

这就是“滚动数组”写法：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, C;
    cin >> n >> C;                     // 物品个数和背包容量
    int w[105], v[105];                // 重量和价值
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    
    int dp[1005] = {0};                // 一维数组，dp[j] 表示容量j的最大价值
    for (int i = 1; i <= n; i++) {
        // 注意：j从C递减到w[i]
        for (int j = C; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[C] << endl;             // 输出答案
    return 0;
}

这个代码更简洁，空间复杂度从 O(n*C) 降到了 O(C)。当容量很大时（比如 10000），二维数组可能爆炸，滚动数组就很有用。

新手容易犯的错误

循环顺序写反
滚动数组里，如果容量 j 从 0 到 C 递增，就会导致“无限背包”错误，即每个物品可以被多次使用。这是最常见的错误。
数组越界
要注意 w[i] 和 C 的大小关系。如果 w[i] > C，那么该物品永远装不进背包，内层循环 j >= w[i] 不成立，直接跳过。但数组下标 dp[j-w[i]] 必须确保 j-w[i] >= 0，所以在内层循环条件里已经保证了。
忘记初始化
全局变量数组会初始化为0，但局部数组要手动 ={0} 或使用 memset。dp数组需要初始化为一个很小的负数（比如 -1e9）来表示“不可能”吗？不一定，这里我们初始为0表示“空背包价值0”，但由于物品重量都是正整数，容量 j 从0开始，所以0是对的。但如果物品价值可能为0，0也可以表示“不拿任何物品”。但是，如果要求恰好装满背包，那么除了 dp[0]=0，其余要初始化为负无穷。普通0-1背包不要求恰好装满，初始化为0即可。
混淆重量和价值的数组下标
dp[j - w[i]] + v[i] 中，容易把 w[i] 和 v[i] 写反，或者把 j-w[i] 写成 j-w[j]，导致编译错误或逻辑错误。
忘记读入多个物品的重量和价值
题目输入格式通常第一行是 n 和 C，后面 n 行每行两个整数（重量和价值）。不要漏读。

完整可运行示例（包含输入输出）

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 输入数据
    int n, C;
    cin >> n >> C;                     // 物品个数 和 背包容量
    int w[105], v[105];                // 重量数组，价值数组
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    
    // 二维动态规划
    int dp[105][1005] = {0};           // dp[i][j] 最大价值，初始0
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= C; j++) {
            dp[i][j] = dp[i-1][j];     // 不拿第i个
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }
    cout << "二维DP结果: " << dp[n][C] << endl;
    
    // 滚动数组优化
    int dp1[1005] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = C; j >= w[i]; j--) {
            dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);
        }
    }
    cout << "一维滚动数组结果: " << dp1[C] << endl;
    
    return 0;
}

输入：

输出：

二维DP结果: 7
一维滚动数组结果: 7

0-1背包问题