动态规划第三课——背包大挑战（0/1背包）（小学版）

课时安排： 120 分钟（内容较难，建议分为两节课或中场休息）
核心口诀：
- “装还是不装，这是一个问题。”
- “不装看上面，装了看剩的空间。”

第一部分：情景引入——贪心算法的“死局”（15分钟）

游戏设定（Minecraft 模式）：
- “史蒂夫（Steve）去下矿，背包只剩下 4 个格子（容量 \(W=4\)）。”
- 面前有 3 个宝物，每个宝物只有一个（强调 0/1 属性）：
  - 宝物1（铁镐）： 占 1 格，价值 15 钻。
  - 宝物2（书本）： 占 3 格，价值 20 钻。
  - 宝物3（钻石）： 占 4 格，价值 30 钻。
挑战学生（让“贪心”失效）：
- 策略 A（挑最贵的）： 拿钻石（价值30）。占满4格。总分 30。
- 策略 B（挑占地最小的）： 拿铁镐（价值15）。剩3格，还能拿书本（价值20）。总分 15+20=35。
- 结论： “你看，光挑贵的不管用，光挑小的也不管用。我们需要一个万能公式，尤其是当东西有 100 个的时候。”

第二部分：核心教学——手动填表（Excel 魔法）（40分钟）

—— 这一步不写代码，只画图，这是整节课的灵魂。

绘制表格：
- 在黑板上画出一个 \(3行 \times 5列\) 的表格（列下标从 0 到 4）。
- 行（物品）： 1-铁镐，2-书本，3-钻石。
- 列（背包临时容量）： 假设背包容量分别是 0, 1, 2, 3, 4 时能装多少。
第一行（只考虑铁镐）：
- “假设世界上只有铁镐这一样东西。”
- 容量 1：装得下吗？装！填 15。
- 容量 4：装完铁镐剩 3 格，没东西装了，还是 15。
- 状态： 第一行填满 0 15 15 15 15。
第二行（关键时刻：书本进场）：
- 场景： “现在轮到书本做决定了。它占 3 格，值 20。”
- 填表互动（假设背包容量是 4）：
  - 选项 A（不拿书本）： “如果不拿书本，那我们在容量 4 的时候最大价值是多少？”
    - 抬头看上一行（是 15）。
  - 选项 B（拿书本）： “如果要拿书本，必须腾出 3 个格子。
    - 书本价值：20。
    - 剩下空间： \(4 - 3 = 1\) 格。
    - 1 格能装的最贵东西是谁？” 查上一行容量 1 的位置（是 15）。
    - 总价值：\(20 + 15 = 35\)。
  - PK 环节： 35（拿） vs 15（不拿）。谁大？35 大！填 35。
第三行（钻石进场）：
- 场景： “轮到钻石。占 4 格，值 30。”
- 填表互动（假设背包容量是 4）：
  - 不拿： 抄上一行（是 35）。
  - 拿：钻石 30 + 剩余空间 0 的价值（0）。总分 30。
  - PK 环节： 35（不拿） > 30（拿）。这次选不拿！
  - 结论： 并不是越贵越好，组合才是王道。

第三部分：公式提炼——把人话翻译成“火星文”（20分钟）

定义坐标：
- \(i\) 代表第几个物品（行）。
- \(j\) 代表背包现在的容量（列）。
- \(dp[i][j]\) 代表：“在前 \(i\) 个物品中选，背包容量为 \(j\) 时的最大价值”。
翻译逻辑：
- “抄上一行的结果” dp[i-1][j]
- “这个物品的价值” value[i]
- “查表看剩下空间的值” dp[i-1][ j - weight[i] ]
究极公式板书： \(dp[i][j] = \max( \underbrace{dp[i-1][j]}_{不拿}, \quad \underbrace{value[i] + dp[i-1][j-weight[i]]}_{拿} )\)
特别提醒（边界判断）：
- “如果背包容量 \(j\) 比物品重量 \(weight[i]\) 还要小，装得下吗？”
- 装不下只能抄上一行，没得选。

第四部分：代码实现（30分钟）

数据结构准备：
- w[i] 存重量，v[i] 存价值。
- dp[105][1005] 二维数组（注意范围要开够）。

核心代码框架：

// 1. 也是双层循环，这很像上一节课的机器人地图
// i 从 1 到 n (遍历每个物品)
for(int i = 1; i <= n; i++) {
        // j 从 0 到 m (遍历每种背包容量的可能性)
        for(int j = 0; j <= m; j++) {

                // 情况 1: 背包太小，根本装不下第 i 个物品
                if(j < w[i]) {
                        dp[i][j] = dp[i-1][j]; // 只能抄上一行
                }
                // 情况 2: 装得下，开始 PK
                else {
                        int 不装 = dp[i-1][j];
                        int 装 = v[i] + dp[i-1][j - w[i]];
                        dp[i][j] = max(不装, 装);
                }
        }
}
cout << dp[n][m]; // 输出表格右下角

调试神技：
- 再次强调：让学生把 dp 数组打印出来。他们会看到一行行数字在变大，非常有成就感。

第五部分：课后总结与伏笔（15分钟）

总结口诀：
- “表格画出来，一行一行填。”
- “当前能不能装？不能装就抄上面。”
- “能装就比赛：抄上面的 vs 自己加剩余。”
伏笔（为滚动数组做准备）：
- “同学们，你们发现没有，我们在算第 3 行的时候，第 1 行的数据还重要吗？是不是只需要看第 2 行就行了？”
- “以后如果我们在这个背包里装 10000 种东西，这个表会太高，内存会爆炸。下次课，教大家一个魔法，把二维表格压扁成一条线！（一维优化）”

配套练习

入门必做： 洛谷 P1048 [NOIP2005 普及组] 采药（最经典的题目，甚至不需要改背景）
巩固练习： 洛谷 P2871 [USACO07DEC] Charm Bracelet S