贪心算法：局部最优到全局最优

贪心算法：从局部最优走向全局最优

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。它的核心思想很直接：总是做出当前看起来最佳的选择，而不从整体最优上加以考虑。这种策略在很多问题中能够得到整体最优解，但也存在无法获得最优解的情况。

在阅读本教程之前，你只需要具备基本的编程思维和简单的数据结构知识（如数组、排序）。接下来，我们将以一种循序渐进的方式，帮你理解贪心算法的工作原理、适用场景以及如何设计和分析一个贪心策略。

1. 什么是贪心算法？

贪心算法可以概括为一句话：每一步都选择局部最优，寄希望于最终结果也是全局最优。

• 局部最优：在当前可选的方案中，选择一个立即收益最大、成本最低或看起来最有利的。
• 不回溯：一旦做出选择，就不再更改，不会像动态规划或回溯那样重新考虑之前的选择。
• 高效性：通常时间复杂度较低，实现简洁。

需要注意，贪心算法并非万能药方。它成功的关键在于问题本身具有贪心选择性质和最优子结构。如果问题不具备这些性质，贪心策略可能只能得到次优解。

2. 贪心算法适用场景：两个关键性质

在尝试用贪心算法解决问题之前，务必检查这两个性质是否成立：

2.1 贪心选择性质

问题的最优解可以通过一系列局部最优选择得到。 也就是说，在做出选择时，不需要依赖未来的选择或子问题的解，只根据当前已有的信息做出最优决策。

验证方法：
假设一个问题的最优解中，某一步没有采取贪心策略的选择，看看能否将这个选择替换为贪心策略的选择，并且不降低整体解的质量。如果可以替换，则通常具备贪心选择性质。

2.2 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。贪心算法通常先做出一个贪心选择，然后求解剩下的子问题。如果剩下的子问题的最优解与已做出的选择能合并成原问题的最优解，那么问题具有最优子结构。

记忆技巧：
一个高度简化的判断方法是问自己：“如果在每一步都选当前最好的，会不会导致后面没有更优的机会？”如果直觉上不会，那很可能适合贪心。

3. 经典问题一：找零钱问题（硬币数量最少）

假设我们有面值为 25 分、10 分、5 分和 1 分的硬币，现在要找给顾客 63 分，如何用最少的硬币数量完成？

3.1 贪心策略

每次都选择面值最大且不超过剩余金额的硬币。

3.2 步骤演示

1. 剩余金额 63，选最大面值 25，使用 2 枚，剩余 63 - 50 = 13。
2. 剩余 13，选最大面值 10，使用 1 枚，剩余 13 - 10 = 3。
3. 剩余 3，选最大面值 1，使用 3 枚，剩余 0。

结果：25×2 + 10×1 + 1×3 = 6 枚硬币。这在现行美国硬币体系下确实是最优解。

3.3 贪心是否总是最优？

如果硬币面值换为 1 分、3 分、4 分，要找 6 分钱：

• 贪心策略：选最大面值 4，剩余 2，再用 1 分两枚 → 总共 3 枚硬币。
• 实际最优：用两枚 3 分硬币，共 2 枚。

这里贪心失败，因为面值不满足某些性质（如规范硬币系统）。因此贪心算法的正确性需要严格证明。

4. 经典问题二：活动选择问题

给定 n 个活动，每个活动有开始时间 start[i] 和结束时间 end[i]。同一时间只能参与一个活动，问最多能参与多少个活动。目标是最大化活动数量。

4.1 贪心策略选择

常见的几种直觉策略：

• 选开始时间最早的？反例：一个活动很早开始却持续一整天。
• 选持续时间最短的？反例：短活动可能与两个长活动重叠，导致失去参与两个的机会。
• 选择结束时间最早的活动，然后排除与之冲突的活动，重复此过程。这是该问题的正确贪心策略。

4.2 算法步骤

1. 将所有活动按结束时间升序排列。
2. 初始化一个变量 last_end = -∞（或一个很小的数），以及计数器 count = 0。
3. 遍历排序后的活动列表：
   • 如果当前活动的开始时间 ≥ last_end，则选择该活动，更新 last_end = 当前活动的结束时间，count += 1。
4. 遍历结束，count 就是最大活动数。

正确性直觉：选择结束最早的活动能为后续留出尽可能多的时间，因此具有贪心选择性质。

5. 经典问题三：分数背包问题

与 0/1 背包不同，分数背包中物品可以切割，取任意比例。给定物品重量 w[i] 和价值 v[i]，背包容量 W，目标是使总价值最大。

5.1 贪心策略

计算每个物品的性价比（价值/重量），按性价比从高到低选择，直到背包装满。

5.2 证明思路

如果存在一个最优解没有按性价比排序取物品，那么可以将性价比低的物品替换为性价比高的，总价值不会降低。因此贪心选择可以得到最优解。

注意：如果是 0/1 背包（物品不可分割），贪心策略往往失败，此时需要动态规划。

6. 贪心算法的设计范式

对于一般问题，设计贪心策略可遵循以下步骤：

1. 转化问题：将优化问题转化为：每一步我们面临一组选择，需要做出一个决定，且决定后问题规模减小。
2. 贪心策略猜测：根据直觉或问题特点，提出一个局部最优的衡量标准，例如“价值最大”“结束最早”“比值最高”等。
3. 排序/预处理：多数贪心策略需要预先对数据进行某种排序，以便快速找到当前最优。
4. 循环选择：使用循环遍历数据，维护当前状态，并在每一步做出不可逆的贪心选择。
5. 正确性验证：尝试用反证法或数学归纳法证明贪心选择的正确性。如果无法证明，应警惕可能会失败。

7. 常见误区与调试技巧

• 试图用数字案例证明算法：几个测试用例通过不代表算法正确，贪心极易在边界情况出错。
• 颠倒选择顺序：如活动选择问题中贪心结束最早，如果误选开始最晚可能得到错误答案。
• 忽视排序：动态规划中的某些问题经过排序也能转化为贪心，但若不排序直接用贪心可能完全错误。

调试方法：

• 构造小规模随机测试数据，用暴力搜索（或已知正确的 DP 解法）对比贪心输出，找出反例。
• 仔细检查是否满足贪心选择性质和最优子结构，尝试在反例中发现破坏哪个性质。

8. 贪心与动态规划的对比

9. 更多经典贪心问题速览

• 哈夫曼编码：数据压缩，每次合并频率最小的两个节点。
• 最小生成树（Prim 算法、Kruskal 算法）：图论中构造连通所有节点的最小边权和树，两种算法都是贪心。
• Dijkstra 最短路径：在非负权图中，每次选择当前距离最小的未访问节点进行松弛。
• 区间调度：活动选择是其特例，还有区间划分、最小延迟调度等变种。

10. 总结与学习建议

贪心算法的精髓在于 “鼠目寸光”但能成大事。它的学习路径建议如下：

1. 掌握经典案例：透彻理解找零钱（注意局限性）、活动选择、分数背包，能白板写出代码。
2. 刻意练习证明：对每个贪心问题尝试写下简短的证明思路，训练自己判断贪心选择性质的能力。
3. 对比反例：刻意寻找贪心失败的例子（如 0/1 背包、具有负权边的 Dijkstra），加深对适用条件的记忆。
4. 刷题拓展：LeetCode 上的贪心标签题可大量练习，从简单到中等，逐步建立自信。

当你下次遇到一个优化问题，不妨先问问自己：“如果我只考虑眼前利益，会不会错过更大的整体利益？”如果答案是否定的，贪心算法或许正是你需要的利器。

祝你学习愉快，算法功力日益精进！