🌟第三课：《贪心王国大冒险》
第三章——贪心的极限与陷阱
🏰 一、故事开场：勇士的危机
1、同学们已经掌握了：
海盗船（选小）
排队接水（选快）
活动选择（选结束早）
2、有的同学，是不是很自信地认为：
“我已经学会贪心了！以后每题都可以用！”
3、汉克老师提醒大家：
“⚠️ 小心！贪心不是万能的！”
于是，带大家来到——
💰宝藏山（背包世界）
🎒 二、第一关：宝藏山（贪心失效！）
1、📖 故事背景
有一个背包，容量 = 10
宝物如下：
| 物品 | 体积 | 价值 |
|---|---|---|
| A | 7 | 36 |
| B | 5 | 25 |
| C | 4 | 20 |
| D | 1 | 15 |
2、🎯 目标
👉让总价值最大！
🧠 第一步：让学生自己“贪心”
（1）汉克老师问：
👉 你会怎么选？
（2）🎯 常见学生答案
👉 选性价比最高的（价值 / 体积）
（3）🚫 结果：
选 D（15/1） → 剩 A (36/7) → 还剩2个空间，剩下的装不下了。
👉 总价值 = 15+36 = 51
（4）😈 汉克老师问
👉 如果选 B + C + D 呢？
体积：5 + 4 + 1 = 10
👉 总价值 = 25 + 20 +15 =60
（5）🎉 结论
👉 ❌ 贪心失败了！
💡 三、为什么贪心失败？
1、🌟 核心原因
👉局部最优 ≠ 全局最优
2、🧠 加深理解
👉 “你选了一个看起来条件最好的，但其实组合的结果，更重要！”
3、🪄 对比理解
| 方法 | 思想 |
|---|---|
| 贪心 | 每一步选最好 |
| 正确解法 | 看整体组合 |
4、🪄 这一类问题属于0/1背包问题
将使用动态规划算法来解决，后面课程中，进行详细讲解。
🎒 四、第二关：分数背包（贪心又行了！）
1、📖 故事升级
这次宝物可以：
👉 ✂️切开！
2、🎯 问题
还是刚才的背包问题
👉 但可以装一部分
3、🧠 贪心策略
👉 按价值 / 体积（性价比）排序
4、💡 举例
| 物品 | 体积 | 价值 | 单位价值 |
|---|---|---|---|
| A | 6 | 30 | 5 |
| B | 5 | 40 | 8 |
👉 优先选 B！
5、🪄 解题步骤
✅ 第一步：计算价值密度
✅ 第二步：排序（从大到小）
✅ 第三步：
能装就全装
不够就装一部分
6、💻 参考程序
#include <iostream> #include <algorithm> using namespace std; struct Node { double w, v; }; bool cmp(Node a, Node b) { return a.v / a.w > b.v / b.w; } int main() { int n, V; cin >> n >> V; Node a[100]; for(int i = 0; i < n; i++) { cin >> a[i].w >> a[i].v; } sort(a, a + n, cmp); double ans = 0; for(int i = 0; i < n; i++) { if(V >= a[i].w) { ans += a[i].v; V -= a[i].w; } else { ans += a[i].v * (V / a[i].w); break; } } cout << ans; }🧠 五、第三关：0/1背包与分数背包
1、📖 看规则
👉 ❌ 能不能切
👉 ✔ 只能选或不选
2、🎯 问题
👉 最大价值？
3、❗ 关键结论
👉 ❌ 0/1背包不能用贪心！
👉 ✅️ 分数背包可以用贪心
4、💣 0/1背包经典错误
👉 用“价值最大”贪心
👉 用“性价比最高”贪心
👉 都可能错！
5、💡 正确方向
👉 需要考虑所有组合
👉 这就是👇
🌟动态规划（下一阶段内容）
🧠 六、本课总结
1、🌟 贪心适用条件
👉局部最优 = 全局最优
2、🌟 能否贪心
| 问题 | 能否贪心 | 原因 |
|---|---|---|
| 海盗船 | ✅ | 选小最优 |
| 分数背包 | ✅ | 可切 |
| 0/1背包 | ❌ | 组合更重要 |
3、🌟 判断口诀
👉 能不能拆？
👉 会不会影响后面？
👉 选一个会不会后悔？
💣 七、容易犯的错误
❌ 错误1：看到极值问题就贪心
👉 错！
❌ 错误2：不会区分两种背包
| 类型 | 特点 |
|---|---|
| 分数背包 | 可切 |
| 0/1背包 | 不可切 |
❌ 错误3：迷信“贪心一定正确”
👉 很多题都会翻车！
❌ 错误4：不做对比验证
👉 一定要试反例！
🎮 八、课堂终极挑战
🎯 挑战1
容量 = 10
物品：
(6,40) (5,29) (5,29)👉 能不能贪心？
🎯 挑战2
👉 如果可以切呢？
🎯 挑战3（思考）
👉 为什么“能切”就可以贪心？
🎉 九、本课结尾
同学们终于明白了：
🌟 贪心不是“万能钥匙”
🌟 而是一种“特殊武器”
汉克老师说：
“真正的高手，不是会用一种方法，而是知道——什么时候用哪种方法！”
学生学会了：
✅ 会用贪心
✅ 会验证贪心策略
✅ 会判断能不能用贪心 ❗（很重要）
