动态规划第四课——快乐水与辣条的无限战争（完全背包）（小学版）

课时安排： 90 分钟
核心目标：
1. 理解 0/1 背包（只能拿一次）与 完全背包（随便拿）的状态转移区别。
2. 从“查上一行”进化到“查当前行”。
3. （进阶）理解为什么 0/1 背包变成一维要倒着算，而完全背包要正着算。

第一部分：情景引入——自助餐的诱惑（15分钟）

回顾“小偷的遗憾”：
- “同学们，上节课我们是‘小偷’，那个超市太穷了，钻石剑只有一把。我们在填表的时候，总是要回头看上一行（过去的状态），生怕拿重了。”
场景升级（自助餐模式）：
- “今天我们发财了！去吃‘无限自助餐’！”
- 菜单：
  - 辣条： 占 2 格胃口，快乐值 3 分。
  - 快乐水： 占 3 格胃口，快乐值 4 分。
- 背包容量： 10 格。
- 老板发话： “管够！随便拿！只要装得下，想拿几根拿几根！”
直觉挑战：
- “如果你有 4 格胃口，只吃辣条，能吃几根？总分多少？”
- 学生回答：2 根，6 分。
- 点题： “看！上节课 4 格只能装 1 根（3分），今天能装 2 根（6分）。这就是完全背包。”

第二部分：核心逻辑——从“回头看”到“看自己”（30分钟）

—— 这一步我们要修改上一节课的那个二维表格。

画图对比（关键步骤）：
- 在黑板上画出二维表格的某一行（比如第 \(i\) 行，物品是辣条，重2值3）。
情景模拟 0/1 背包（旧知识）：
- “假设现在背包容量是 4。如果我们决定拿辣条。”
- “因为每样只有 1 个，所以我们拿完之后，剩下的空间（\(4-2=2\)），必须去上一行（没拿过辣条的状态）找。”
- 板书公式（0/1）： dp[i][j] = 价值 + dp[i-1][ j-weight ] （去找老账本）
情景模拟完全背包（新知识）：
- “现在是自助餐。还是容量 4，还是决定拿辣条。”
- “拿了一根之后，剩下的空间（\(4-2=2\)），能不能再拿辣条？能！”
- “所以我们不需要去上一行找，我们直接在这一行（第 \(i\) 行）找容量 2 的最优解。”
- “如果在容量 2 的时候我们已经拿过一根辣条了（分数为3），那现在容量 4 再拿一根，就是 \(3+3=6\) 分！”
- 板书公式（完全）： dp[i][j] = 价值 + dp[i][ j-weight ] （去找新账本，注意是 \(i\) 不是 \(i-1\)）
总结区别：
- 0/1 背包 \(\rightarrow\) 继承上一行的结果。
- 完全背包 \(\rightarrow\) 继承这一行刚才算出来的结果。

第三部分：魔法降维——压扁表格（25分钟）

—— 既然完全背包是“继承这一行”，那我们为什么要存上一行呢？直接用一行不就行了？

引入“滚动数组”（一维优化）：
- “同学们，既然完全背包只需要看这一行前面的格子，那上一行的数据是不是就没用了？”
- “我们把表格压扁，只留一行格子！”
数轴演示（正序 vs 倒序）：
- 画一条数轴（一维数组）。
- 完全背包（大步向前走）：
  - “我想吃辣条（重2）。我从左往右填。”
  - dp[2] = 3 （吃1根）
  - 走到 dp[4]：我想再吃一根。回头看 dp[2]，发现是 3。于是 dp[4] = 3 + 3 = 6。
  - 结论： 从左往右（正序），就像滚雪球，越滚越大，刚好符合“无限拿”。
- 0/1 背包（倒车请注意）：
  - “如果只能拿 1 根，能不能从左往右填？”
  - “dp[2] 变成了 3。走到 dp[4]，回头看 dp[2] 也是 3，加起来变成 6。坏了！ 只有一根辣条，你却吃了两根！”
  - 结论： 如果只能拿 1 个，必须从右往左（倒序），这样回头看的时候，看到的是还未更新的“旧数据”（也就是上一行的数据）。
视觉口诀：
- 无限拿（完全） \(\rightarrow\) 正着跑（利用新数据）。
- 只能拿1个（0/1） \(\rightarrow\) 倒着跑（避开新数据）。

第四部分：代码落地（20分钟）

代码修改：

让学生拿出上节课的二维代码。
第一步： 把 dp[i][j] 全部改成 dp[j]。
第二步： 修改内层循环的方向。

// 0/1 背包（回顾）
for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) { // 倒序！
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
}

// 完全背包（新课）
for(int i = 1; i <= n; i++) {
        for(int j = w[i]; j <= m; j++) { // 正序！从能装得下开始，一直往后滚
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
}

实战练习：
- 洛谷 P1616 疯狂的采药（提醒： 这题数据很大，要开 long long，正好教一下数据范围）。

教练备课 Tips（针对 5-6 年级）

过渡的难点：
- 从二维 dp[i][j] 突然跳到一维 dp[j]，有些孩子会懵。
- 话术建议：不要说是“优化”，要说是“偷懒”。“老师不想写 [i] 和 [i-1] 了，手酸。既然完全背包只看自己这一行，那我就只开一个数组 dp[]，一边算一边更新自己。”
关于初始化：
- 这里的例子是求最大价值，初始化为 0 即可。
- 如果你打算布置“零钱兑换”（求最小硬币数），一定要在下课前预警：求最小值时，数组要初始化成一个很大的数（如 99999），不然最小值永远是 0！
为什么先讲二维再讲一维？
- 5-6 年级的孩子，逻辑思维还不够强。二维表格能让他们看到“历史数据”和“当前数据”的位置关系。有了这个视觉基础，再讲“正序/倒序”的覆盖原理，他们才能听懂，否则就是死记硬背。