GESP 六级 第 08 讲：简单背包

本讲定位：官方大纲知识块 4 点名「简单背包」。客观题里单选第 15 题固定考「01 背包一维写法的填空」，判断题固定考「内层正序会怎样」；编程题第 1 题也反复出背包变形——2025 年 12 月「道具商店」是 01 背包，2023 年 9 月「小杨买饮料」是带 no solution 的最小费用型。

本讲要把三件事讲死：一维写法为什么要逆序、正序就是完全背包、容量太大时换维度。

本讲建议安排两周。

对应官方大纲：六级知识块 4「简单动态规划」——简单背包。

前置知识：六级第 07 讲（一维 DP 四步法）、五级第 08 讲（贪心 vs DP、0-1 背包反例）。

代码说明：本讲代码均已用 g++ 11.5（-std=c++11）编译运行验证；「道具商店」在官方样例上输出一致，各程序另与 $2^n$ 枚举子集的暴力对拍（$n \le 15$，各数百组）。

1. 01 背包：从二维说起

$n$ 件物品，第 $i$ 件重 $w_i$、值 $v_i$，每件最多拿一次。背包容量 $W$，求能装的最大总价值。

五级第 08 讲讲过：可以切开的是「部分背包」，用贪心；不能切开的就是 01 背包，只能 DP。

1.1 四步法（沿用六级第 07 讲）

步骤 内容
① 状态 f[i][j] = 只考虑前 $i$ 件物品、容量为 $j$ 时的最大价值
② 转移 第 $i$ 件拿还是不拿：不拿 → f[i-1][j]拿（要求 $j \ge w_i$）→ f[i-1][j-w[i]] + v[i]**f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])**
③ 边界 f[0][j] = 0（一件都不考虑，价值 0）
④ 答案 f[n][W]

📌 和六级第 07 讲打家劫舍的转移长得几乎一样：都是「这一个拿不拿，取 max」。区别在于背包多了一个「容量」维度——拿了要占地方。

1.2 二维代码与手填表

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

int main() {
    int n = 4, W = 5;
    int w[5] = {0, 2, 1, 3, 2};        // w[1..4]
    int v[5] = {0, 3, 2, 4, 2};        // v[1..4]
    int f[5][6] = {{0}};

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= W; ++j) {
            f[i][j] = f[i - 1][j];                                   // 不拿第 i 件
            if (j >= w[i])
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);   // 拿第 i 件
        }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= W; ++j) cout << f[i][j] << " ";
        cout << endl;
    }
    return 0;
}

输出的 f 表（行 = 考虑前 $i$ 件，列 = 容量 $j$）：

$i \backslash j$ 0 1 2 3 4 5
0 0 0 0 0 0 0
1（$w=2,v=3$） 0 0 3 3 3 3
2（$w=1,v=2$） 0 2 3 5 5 5
3（$w=3,v=4$） 0 2 3 5 6 7
4（$w=2,v=2$） 0 2 3 5 6 7

（实测验证 ✅）答案 f[4][5] = 7——拿第 1 件和第 3 件：重 $2+3=5$ 正好装满，值 $3+4=7$。

📌 让学生逐格填这张表，特别注意每一格都只看上一行的两个位置（正上方、左上方偏 $w_i$ 格）。看清「只依赖上一行」，就能理解下一节为什么能压成一维。

2. 压成一维：为什么必须逆序 ★★

2.1 压缩的依据

上表里，f[i][j] 只用到 f[i-1][...]——上一行。既然只需要上一行，就不必存整张表，用一个一维数组反复覆盖即可。

for 每件物品 i:
    for j = W 降到 w[i]:
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);