GESP 7级

01背包问题

7级 · DP/图论/搜索

📖 一句话理解

你有一个背包，最多能装 W 千克的东西。面前有 n 个物品，每个物品有自己的重量和价值。每个物品只能选或不选（01的含义：0代表不选，1代表选）。你要怎么装，才能让背包里物品的总价值最大？
💡 为什么重要？
背包问题是动态规划（DP）的入门经典。学好它，你就理解了DP的核心思想："把大问题拆成小问题，记录每个小问题的答案，最终拼出大问题的答案"。几乎所有DP问题的思路都从这里开始。在GESP 7级考试中，背包问题是必考重点。
📋 前置知识（必须先掌握）
  • 一维数组和二维数组：知道 int dp[100] 和 int dp[100][100] 怎么用
  • for循环嵌套：至少会写两层for循环
  • max()函数：取两个数中较大的那个
  • 基本的递归概念：函数调用自己（不用很深，知道有这回事就行）

🧠 动态规划到底是什么？

想象你站在岔路口，要找一条到终点的最短路。你不知道哪条路最好，怎么办？

DP的做法是：从终点往回推，先算"离终点最近的每条路有多长"，再算"再远一步的每条路有多长"……一步步推回到起点。

🔑 DP三步走（适用于所有DP问题）
  1. 定义状态：dp[i][w] 代表什么？（这里代表：前i个物品、背包容量为w时的最大价值）
  2. 找转移方程：dp[i][w] 怎么从更小的子问题得到？
  3. 确定初始值和遍历顺序：哪些值是已知的？先算谁后算谁？

📐 01背包的核心思路

第一步：定义状态

dp[i][w] = 从前 i 个物品中选，背包容量为 w 时，能获得的最大价值。

为什么是二维的？因为我们需要记录两个信息：用到了前几个物品？背包还剩多少容量？

第二步：转移方程（最关键！）

对于第 i 个物品，我们有两种选择：

两种选择取最大值：

📐 核心转移方程
dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i])

含义：不选第i个物品 vs 选第i个物品，取较大值

第三步：初始值

当没有任何物品可选时（i=0），最大价值是0；当背包容量为0时，最大价值也是0。所以 dp[0][w] = 0，dp[i][0] = 0。

🔢 手动推演：用例子理解

假设3个物品，背包容量5：

📊 dp表格推演（部分关键值）

dp[1][2] = max(dp[0][2], dp[0][0]+3) = max(0, 3) = 3 ✓
dp[2][5] = max(dp[1][5], dp[1][2]+4) = max(3, 3+4) = 7 ✓
dp[3][5] = max(dp[2][5], dp[2][1]+5) = max(7, 0+5) = 7 ✓
最终答案：dp[3][5] = 7（选物品1+物品2，总重5，总价值7）

💻 二维DP代码（最直观，建议先看这个）

💻 完整示例代码（二维版本）
#include <iostream>
#include <algorithm>   // max()函数
using namespace std;

int main() {
    int n = 3;          // 物品数量
    int W = 5;          // 背包最大容量
    int weight[] = {0, 2, 3, 4};  // 每个物品的重量（下标从1开始）
    int value[] = {0, 3, 4, 5};   // 每个物品的价值（下标从1开始）

    // dp[i][w] = 前i个物品、容量为w时的最大价值
    // 多开一行一列，第0行和第0列初始为0
    int dp[4][6] = {0}; // dp[0..3][0..5]，全部初始化为0

    // 外层循环：逐个考虑每个物品（i从1到n）
    for (int i = 1; i <= n; i++) {
        // 内层循环：逐个考虑每种容量（w从1到W）
        for (int w = 1; w <= W; w++) {
            // 先假设不选第i个物品，价值不变
            dp[i][w] = dp[i-1][w];

            // 如果背包容量够装第i个物品，考虑选它
            if (w >= weight[i]) {
                // 选第i个物品的价值 vs 不选的价值，取大的
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << "最大价值: " << dp[n][W] << endl;  // 输出答案
    return 0;
}

⚡ 空间优化：一维DP（考试常用写法）

上面的二维代码中，第 i 行其实只用到了第 i-1 行的数据。所以我们可以只用一行数组，把空间从 O(n×W) 降到 O(W)。

⚠️ 关键：内层循环必须逆序！
为什么？如果正序遍历，dp[w-weight[i]] 可能已经在本轮被更新过了，相当于同一个物品被选了多次（那就变成完全背包了！）。
逆序保证每个物品只被选一次。
📐 一维空间优化
dp[w] = max(dp[w], dp[w-w[i]] + v[i])

内层循环：从大到小遍历 w（从 W 到 weight[i]）
💻 完整示例代码（一维优化版）
#include <iostream>
#include <algorithm>   // max()函数
using namespace std;

int main() {
    int n = 3;          // 物品数量
    int W = 5;          // 背包最大容量
    int weight[] = {2, 3, 4};   // 每个物品的重量
    int value[] = {3, 4, 5};    // 每个物品的价值

    int dp[6] = {0};    // 一维数组，dp[w] = 容量为w时的最大价值
                         // 初始全部为0

    for (int i = 0; i < n; i++) {         // 遍历每个物品
        for (int w = W; w >= weight[i]; w--) {  // ⚠️ 逆序！从大到小！
            // dp[w]：不选当前物品（保持原值）
            // dp[w-weight[i]] + value[i]：选当前物品
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }

    cout << "最大价值: " << dp[W] << endl;  // 输出答案
    return 0;
}

❓ 常见疑问

🤔 为什么逆序就保证每个物品只选一次？
逆序时，计算 dp[5] 时 dp[3] 还是上一轮的旧值（没被当前物品更新过），所以不会重复选择。如果正序，计算 dp[3] 时已经把当前物品放进去了一次，到 dp[5] 又用 dp[3] 来算，就等于同一个物品选了两次。

🚨 易错点

⚠️ 常见错误汇总
  1. 一维DP内层正序遍历：这是最常见的错误！01背包内层一定要逆序（从大到小），完全背包才正序。
  2. 数组越界：dp数组要开 W+1 大小（因为下标从0到W），忘记+1会越界。
  3. 忘记初始化：dp数组要初始化为0，否则会有随机值干扰结果。
  4. weight[i]越界判断：选物品前一定要检查 w >= weight[i]，不然会访问负数下标。
  5. 下标混乱：二维版本从 i=1 开始，weight/value 下标也要从1开始；一维版本从 i=0 开始。两种写法下标规则不同，要分清！

🎯 练习建议

📝 循序渐进练习路径
  1. 第一步：先在纸上手动推一个小例子（比如3个物品、容量5），写出完整的dp表格。
  2. 第二步：照着二维代码，自己敲一遍，提交到 OJ 验证。
  3. 第三步：改写成一维版本，注意逆序遍历，再次提交验证。
  4. 第四步：做以下经典题目练习：
    • P1048 采药（洛谷入门题）
    • P1060 开心的金明
    • P1049 装箱问题（变形：能否恰好装满）
  5. 第五步：对比01背包和完全背包的代码差异（内层循环方向！），加深理解。
已是第一个 📖 返回主目录 下一个：完全背包 →