动态规划第 七 课——神秘礼盒的填充魔法 （小学版）

—— 不求最贵，但求填满（求方案总数）

• 课时时长：90 分钟
• 适用阶段：已掌握 0/1 背包求最大价值（Max），准备进阶。

• 核心目标：

  1. 思维翻转：从“贪心”（求 Max）转变为“统计”（求 Sum）。
  2. 模型构建：理解“加法原理”在 DP 中的应用，掌握方程 dp[j] += dp[j - w]。
  3. 核心难点：理解 dp[0] = 1 的物理含义（“什么都不装”也是一种合法方案）。
  4. 实战准备：为课后挑战 P1164 打下坚实基础。

• 所需教具：

  • 一个透明的盒子（贴上标签“容量 5”）。
  • 若干标有重量的积木或球（如 1, 2, 2, 3, 5）。
  • 黑板磁力贴。

课程时间表

详细教学流程

1. 引入：完美的强迫症患者 (15 min)

• 情景设置：

  “魔法学院要给贫困山区的孩子寄礼物。我们有一个礼盒，容量刚好是 5kg。国王有个奇怪的要求：必须刚好填满，不能留一点缝隙，也不能盖不上盖子。”

• 互动挑战：

  • 仓库清单（每样只有 1 个）：

    • 魔法书：1kg
    • 水晶球：2kg
    • 玩具熊：2kg （注意：虽然都是2kg，但这是两个不同的东西！）
    • 重铁块：3kg

  • 提问：请同学们在纸上画一画，有几种方法能刚好凑出 5kg？

  • 学生尝试：

    1. 魔法书(1) + 水晶球(2) + 玩具熊(2) = 5
    2. 水晶球(2) + 重铁块(3) = 5
    3. 玩具熊(2) + 重铁块(3) = 5

  • 答案：3种。

• 痛点引出：

  • “现在只有 4 个物品，你们能算出来。如果仓库里有 100 个物品，容量是 1000kg，你们的脑子就要‘爆栈’了。我们需要请出 DP 魔法。”

2. 推导：河流汇聚图 (20 min)

• 回顾对比：

  • 以前（0/1背包）：我们是“寻宝猎人”。遇到一个宝物，我们想：“拿了它价值会不会更高？”（取 Max）。
  • 今天（求方案数）：我们是“统计员”。遇到一个物品，我们想：“拿它是一种办法，不拿它也是一种办法，我要把所有办法加起来！”

• 可视化演示（板书画图）：

  • 画一个大池塘，写着 dp[j]（填满容量 j 的方法数）。

  • 画两条河流流入池塘：

    • 左边的河（不拿这个物品）：方法数直接流过来，等于 dp[j]（旧）。
    • 右边的河（拿这个物品）：假设物品重 w，那么只要知道“填满 j-w 有多少种方法”，这些方法加上这个物品，就能变成填满 j 的方法。所以流过来的是 dp[j-w]。

  • 结论：总水量 = 左边 + 右边。

  • 公式诞生：dp[j] = dp[j] + dp[j - w]。

3. 核心：空盒子的哲学 (25 min) <-- 难点攻克

• 填表模拟（一维数组倒序）：

  • 我们来填满容量 5。物品：书(1), 球(2), 熊(2), 铁(3)。
  • 灵魂发问：dp[0] 是多少？
    • “如果要填满容量为 0 的盒子（也就是什么都不装），有几种方法？”
    • 学生可能回答 0。
    • 老师纠正：“‘发呆’也是一种方法！ 把盖子直接盖上，是不是刚好填满了 0 的空间？是的！所以 dp[0] = 1。”
    • 强调：如果 dp[0]=0，后面的加法全是 0，程序就废了。

• 手推第二轮（以物品“球 2kg”为例）：

  • 假设之前已经处理了“书 1kg”，现在 dp 数组里 dp[1]=1, dp[0]=1，其他是0。

  • 现在来处理“球 2kg”：

    • 算 dp[3]：不拿球(0种) + 拿球(查 dp[3-2] 即 dp[1] 的 1 种) = 1 种。
    • 算 dp[2]：不拿球(0种) + 拿球(查 dp[2-2] 即 dp[0] 的 1 种) = 1 种。

  • 让学生看到数据是如何像波浪一样累加起来的。

4. 代码：代码大变身 (20 min)

• 找茬游戏：

  • 在屏幕上放出标准的 0/1 背包求最大价值代码。
  • 请同学上来“做手术”，把它改成求方案数代码。

  部位	求最大价值 (旧)	求方案数 (新)
  初始化	dp[0...m] = 0	dp[0] = 1, dp[1...m] = 0
  状态转移	dp[j] = max(dp[j], dp[j-w] + v)	dp[j] = dp[j] + dp[j-w]
  含义	v (价值) 很重要	v 完全没用，只看 w (重量)

• 完整代码模板：

  int dp[10005]; 
  int w[105]; // 物品重量
  
  // 1. 初始化：空盒子也是一种方案
  dp[0] = 1; 
  
  for(int i = 1; i <= n; i++) { // 遍历物品
          for(int j = m; j >= w[i]; j--) { // 倒序遍历容量
                  // 2. 累加方案：旧方案 + 新方案
                  dp[j] = dp[j] + dp[j - w[i]];
          }
  }
  cout << dp[m]; // 输出填满背包的方法数
  

5. 总结与作业：Boss 战预告 (10 min)

• 要点回顾：

  1. 初始化 dp[0]=1。
  2. 方程用 + 不用 max。
  3. 0/1 背包要倒序。

• 课后作业（重头戏）：

  • P1164 小A点菜

给教练的备课建议

1. 关于 dp[j] += ... 的简写：

   • 给小学生讲的时候，建议先写完整形式 dp[j] = dp[j] + dp[j-w]，等他们理解了再教 +=。完整形式更能体现“两河汇聚”的物理含义。

2. 关于数据范围：

   • P1164 的数据算出来 int 就够了。但可以顺便提一句，如果方案特别多（比如硬币凑数），可能会爆 int，那时就要用 long long。这是很好的竞赛习惯培养。

3. 调试技巧：

   • 如果学生算出的答案是 0，99% 是因为忘了 dp[0]=1。
   • 如果算出的答案特别大，可能是内层循环写成了正序（变成了完全背包，东西可以重复拿）。这是一个非常好的 Debug 教学点。