本课时有配套视频讲解，购买后即可观看（永久有效）
贪心法
一、课上练习
编程练习
二、知识总结
✨ 贪心法的核心思想
贪心法（Greedy Algorithm）的核心思想就是：每次都选最好的！ 在每一步决策中，都选择当前看起来最优的选项，通过一系列局部最优的选择，最终达到全局最优。
✨ 贪心法的应用场景
贪心法适用于可通过局部最优解推出全局最优解的问题，通常具有以下特征：
- 求"最"值或最优状态的问题
- 需要多步操作的问题
- 每一步的选择不会影响后续步骤的最优选择（即具有贪心选择性质）
需要注意的是，并非所有求最优解的问题都适合用贪心法。如果局部最优不能推出全局最优，则需要使用动态规划等其他方法。
✨ 贪心法的原理
使用贪心法解题的一般步骤：
- 识别问题类型：判断问题是否具有贪心选择性质
- 归纳贪心公式：确定每一步的贪心策略，即每一步如何选择最优
- 通过反例确认公式正确性：尝试找反例来验证贪心策略是否能得到全局最优解
✨ 贪心案例
以下排序算法都运用了贪心法的思想：
- 选择排序：每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾
- 冒泡排序：每次比较相邻元素，将较大（或较小）的元素向后移动，每轮将最大值"冒泡"到末尾
- 插入排序：每次将未排序部分的第一个元素插入到已排序部分的正确位置
这些排序算法的共同点是：每一步都做出当前最优的选择（选最小的、交换错误的、插入正确位置），最终达到整体有序的目标。
✨ 贪心法的执行示例
经典贪心问题：找零钱
问题： 用最少的硬币凑出 41 元，硬币面值有 25、10、5、1 元。
贪心策略： 每次优先使用面值最大的硬币。
| 步骤 | 剩余金额 | 贪心选择 | 使用硬币 | 原因 |
|---|---|---|---|---|
| 1 | 41 | 能用 25 吗？能 | 25元 x 1 | 41 >= 25，优先选最大面值 |
| 2 | 16 | 能用 25 吗？不能 | - | 16 < 25 |
| 3 | 16 | 能用 10 吗？能 | 10元 x 1 | 16 >= 10 |
| 4 | 6 | 能用 10 吗？不能 | - | 6 < 10 |
| 5 | 6 | 能用 5 吗？能 | 5元 x 1 | 6 >= 5 |
| 6 | 1 | 能用 5 吗？不能 | - | 1 < 5 |
| 7 | 1 | 能用 1 吗？能 | 1元 x 1 | 1 >= 1 |
| 8 | 0 | 结束 | - | 剩余为 0 |
结果： 使用 4 枚硬币（25+10+5+1），这确实是最优解。
贪心失败的例子
问题： 硬币面值为 1、3、4 元，凑出 6 元。
- 贪心策略：4 + 1 + 1 = 3 枚硬币
- 最优解：3 + 3 = 2 枚硬币
这说明贪心法并不总是正确的！当硬币面值不满足特定条件时，贪心法可能得不到最优解，需要用动态规划。
✨ 贪心法的解题步骤
例题：排队接水问题
有 n 个人排队接水，第 i 个人接水需要 t_i 分钟。如何安排顺序使得所有人的总等待时间最小？
解题步骤：
- 识别问题类型：求"最小总等待时间"，是一个求最值的多步操作问题，考虑贪心
- 归纳贪心策略：让接水时间短的人先接。直觉上，让快的人先完成，后面所有人等待的时间都少
- 验证策略：假设有两个人 A（3分钟）和 B（5分钟）
- A先B后：A等0分钟 + B等3分钟 = 总等待3分钟
- B先A后：B等0分钟 + A等5分钟 = 总等待5分钟
- 让快的先接确实更优
- 实现：将接水时间排序后，计算总等待时间
1// 按接水时间从小到大排序
2sort(t, t + n);
3int total_wait = 0;
4int current_wait = 0;
5for (int i = 0; i < n; ++i) {
6 total_wait += current_wait; // 第 i 个人的等待时间
7 current_wait += t[i]; // 更新累计时间
8}
9cout << total_wait << endl;✨ 贪心法的常见错误
- 没有验证贪心策略的正确性：直接想一个"看起来合理"的策略就开始写代码，没有通过举例或反例来验证。很多贪心策略直觉上合理但实际上是错误的
- 贪心策略不够具体：比如"每次选最好的"这种描述太笼统，需要明确"最好"的衡量标准是什么（最大？最小？比值最大？）
- 把不适合贪心的问题用贪心来做：典型的例子是 0/1 背包问题，按性价比贪心并不能得到最优解，需要使用动态规划
- 排序方向搞反：比如排队接水应该按时间从小到大排，但写成了从大到小
- 忽略边界情况：例如只有 1 个人时不需要等待，或者所有人接水时间相同时任意顺序都一样