《Hello 算法》贪心算法全解：从硬币找零看“局部最优”如何逼近“全局最优”

贪心算法（greedy algorithm）是求解最优化问题的一类通用算法策略：在每一轮决策中只选取“当下看起来最优”的选项（即局部最优解），期望通过一系列局部最优选择最终拼出全局最优解。本文以《Hello 算法》贪心法章节为核心，结合仓库中硬币找零贪心实现与动态规划实现的真实源码，讲解贪心与动态规划的分野、贪心选择的失效反例、贪心法的两大判定特性、解题三步骤以及典型应用，读完你将能判断“什么样的优化问题适合用贪心、什么样的只能用动态规划”。

贪心算法的核心思想：让局部最优自然累积

贪心法的思想非常朴素——既然最终目标是全局最优，那就在每个决策时刻都贪心地选择当前最有利的方案，然后缩小问题规模，如此往复直至问题解决。这种“走一步看一步、绝不回头修正”的风格，与动态规划形成了鲜明对比。

从实现层面看，贪心算法不需要维护一张状态表，也不需要在多个候选解之间回溯比较，往往十几行代码即可完成，这正是它在工程中广受欢迎的原因。

与动态规划的本质区别

在《Hello 算法》中，贪心与动态规划常常被放在一起讨论，两者都擅长解决最优化问题、都依赖“最优子结构”，但工作原理截然不同：

• 动态规划：决策当前状态时，会参考此前所有阶段决策的历史，利用过去子问题的最优解来构造当前子问题的最优解，本质上是“自底向上”或“自顶向下”地对整个解空间做枚举与剪枝。
• 贪心算法：不回头考虑过去的决策，只依据当下信息做一步“看起来最好”的选择，持续把问题收窄为更小的子问题，直到得出最终答案。

直观理解：动态规划像是一个“全盘考虑后做决定”的策略家，贪心则像“只看眼前最大利益、一直往前走”的行动派。仓库中 贪心小结 对此总结为：贪心反复进行贪心选择，每轮都将问题转化为更小的子问题；与动态规划相比，贪心的时间复杂度通常更低。

硬币找零问题：建立贪心直觉的经典样例

要理解贪心法，最好的方式是通过一道具体问题建立直觉。《Hello 算法》选择了硬币找零问题作为开篇示例，它此前已在完全背包问题一节中出现过，读者会有熟悉感。

问题定义：给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i - 1]$，目标金额为 $amt$。每种硬币可以无限次使用，求凑出目标金额所需的最少硬币数；若无法凑出，返回 $-1$。

贪心策略：选“不超过剩余金额的最大硬币”

贪心策略非常直观：给定目标金额，每次都选择一张面值不超过剩余金额、且尽可能大的硬币，重复该过程直到金额凑满。仓库中日文版实现位于 coin_change_greedy.py，其核心逻辑如下：

def coin_change_greedy(coins: list[int], amt: int) -> int:
    """硬币找零：贪心法"""
    # 假设 coins 已按升序排序
    i = len(coins) - 1
    count = 0
    # 循环贪心选择，直到剩余金额为 0
    while amt > 0:
        # 找到不超过剩余金额的最大面值硬币
        while i > 0 and coins[i] > amt:
            i -= 1
        # 选择硬币 coins[i]
        amt -= coins[i]
        count += 1
    # 未找到可行解时返回 -1
    return count if amt == 0 else -1

代码的关键点在于：由于输入 coins 按升序排列，代码从最大面值硬币（下标 len(coins) - 1）开始向内收缩指针 i，每轮用“内部 while”跳过所有面值大于剩余金额的硬币，找到最大的可用面值后立即扣减金额并计数。整个实现只有一次线性扫描，没有任何嵌套的完整解空间搜索，这正是贪心法“短小精悍”的体现。

以仓库驱动代码中的正例验证：coins = [1, 5, 10, 20, 50, 100]、amt = 186 时，贪心法依次取 100、50、20、10、5、1 各一张，恰好 6 枚得到最优解。

贪心的优点与局限：为什么硬币组合不同结论不同

优点：简单、直接、高效

贪心算法不仅实现直观，通常还拥有很高的效率。仍以硬币找零代码为例：设最小硬币面值为 $\min (coins)$，由于每轮至少消耗 $\min (coins)$ 的金额，贪心选择的循环次数至多为 $amt\mathrm{/}\min (coins)$ 次，因此时间复杂度的量级为 $O(amt\mathrm{/}\min (coins))$。相比之下，动态规划解法（见仓库 coin_change.py）需要维护 $(n + 1) \times (amt + 1)$ 的状态表，时间复杂度为 $O(n \times amt)$。贪心的复杂度比动态规划低了整整一个数量级，这正是“能贪就贪”的底气所在。

局限：并非所有硬币组合都成立

然而硬币面值的具体组合会影响贪心法的正确性。下图展示了贪心法会失效的两种反例：

• 正例 $coins = [1, 5, 10, 20, 50, 100]$：该组合具有“规范硬币系统”的特点，对任意目标金额 $amt$，贪心法都能找到最优解；
• 反例一 $coins = [1, 20, 50]$，目标 $amt = 60$：贪心会先取 50，再取 10 枚 1 元硬币，共 $50 + 10 \times 1 = 60$，合计 11 枚；而动态规划能找到 $20 + 20 + 20$，只需 3 枚；
• 反例二 $coins = [1, 49, 50]$，目标 $amt = 98$：贪心先取 50，再用 48 枚 1 元补齐，合计 49 枚；动态规划得到 $49 + 49$，只需 2 枚。

上述反例均可在仓库 coin_change_greedy.py 的驱动代码中实际运行复现：程序会输出贪心得到的硬币数，并对比打印动态规划的真正最优解（3 与 2）。这说明硬币找零问题本质上并不保证贪心选择能导出全局最优解，极端情况下贪心甚至可能给出“非常糟糕”的结果，因此该问题更适合交给动态规划求解。

贪心法的适用场景：两类情况

综合来看，贪心算法适用的场景可以归纳为两类：

1. 能够保证最优解的情况：此时贪心往往是最佳选择。因为它通常比回溯与动态规划都更高效，代码更简洁、运行更快；
2. 只能求近似最优解的情况：贪心依然有价值。许多复杂优化问题（如大规模调度、NP-hard 类问题）求全局最优本身就极其困难，此时以较高效率获得一个“足够好”的近似解，在工程中同样具有现实意义。

贪心法的两大特性：适用性的判据

那么，什么样的最优化问题适合用贪心？换一种问法——贪心法何时能保证得到全局最优解？

相比动态规划，贪心的适用条件更加苛刻，核心考察以下两条性质：

• 贪心选择性（greedy choice property）：只有当一个“局部最优”的选择总能导向全局最优解时，贪心法才能保证正确。即：局部最优选择本身就是全局最优解的一部分，不需要修正；
• 最优子结构（optimal substructure）：原问题的最优解中包含子问题的最优解。该性质在《Hello 算法》动态规划章节中已系统介绍，此处不再重复。需要注意，有些问题即使最优子结构并不直观，仍可能可以用贪心求解。

这两条性质中，“最优子结构”已有成熟的理论框架，真正的难点在于验证“贪心选择性”。单看文字定义它似乎很简单，但现实中为具体问题证明贪心选择性往往非常困难。

以硬币找零为例：举一个反例就能轻易否定贪心选择性（如 $coins=[1,49,50], amt=98$），但要证明“某组硬币对任意金额贪心都成立”却很难。如果被问到“什么样的硬币组合满足贪心可用”，多数人只能依赖直觉和零散例子给出含糊答案，而很难给出严格的数学刻画。

事实上，这一看似“常识”的问题在学术上直至 2005 年才被完整解决。原文引用了相关论文：

有论文给出了判定算法：对于某组硬币面额组合，是否对任意金额都能用贪心法求得最优解，可以在 $O(n^3)$ 时间内判定。

Pearson, D. A polynomial-time algorithm for the change-making problem[J]. Operations Research Letters, 2005, 33(3): 231-234.

这个例子很好地说明：贪心选择性不是“凭感觉就能判定”的平凡性质，即便是一道看似简单的找零题，其理论证明也颇具深度。

贪心法的解题三步骤：从建模到证明

《Hello 算法》将贪心求解过程归纳为三大步骤：

1. 问题分析：梳理状态定义、优化目标与约束条件，充分理解问题结构。这一阶段与回溯、动态规划解法中的分析是共通的；
2. 确定贪心策略：明确每一步应如何做出贪心选择，使策略能在每轮缩小问题规模，最终解决整个问题；
3. 证明正确性：通常需要论证问题具备“贪心选择性”与“最优子结构”，这一步往往要用到数学归纳法、反证法等严谨证明手段。

其中“确定贪心策略”是解题核心，但它常常并不容易，主要有两方面的原因：

• 问题之间贪心策略差异巨大：不少问题的贪心策略比较直观，稍加思考与试错即可得到；但复杂问题中，贪心策略可能非常隐蔽，此时相当考验解题者的经验积累与算法功力；
• “看似合理”的策略可能只是部分正确：即使信心满满地设计好贪心策略、写完代码并提交，也可能栽在某些测试用例上。上一节的硬币找零 $coins=[1,20,50]$ 就是典型：按“先取最大面值”的直觉去贪，却在 $amt=60$ 时得到非最优的 11 枚。

正确性证明：为何必须严谨

为保证算法正确，必须对贪心策略做严格数学证明，通常采用反证法或数学归纳法：

• 反证法：假设贪心解不是最优解，通过局部最优特性推导矛盾，从而证明贪心选择必然在某个全局最优解中出现；
• 数学归纳法：证明贪心选择后剩余的子问题仍可用同一策略递归求解，且归纳合并后得到全局最优。

但正确性证明本身也常常不易。当暂时没有证明头绪时，工程实践中的常见做法是：先用大量测试用例运行代码进行调试与对拍，一边修正贪心策略、一边积累对问题结构的认识，再回头补全证明。

贪心法典型问题：仓库中的实践印证

贪心法适用于满足“贪心选择性”和“最优子结构”的优化问题。《Hello 算法》列举了若干经典贪心问题，其中不少在仓库的贪心章节中配有独立的动画演示与完整代码，可以作为继续深入的学习路径：

• 硬币找零问题：某些硬币组合下贪心恒得最优解，详见本文示例及 coin_change_greedy.py；
• 分数背包问题：物品可按比例分割，每次贪心选择“单位价值（价值/重量）最高”的物品即可在特定条件下取得最优解，参考分数背包问题 与 fractional_knapsack.py，该问题的贪心正确性可由反证法证明；
• 区间调度问题：若干任务占用不同时间段，目标是完成尽可能多的任务；每次选择“结束时间最早”的任务即为贪心最优策略；
• 股票买卖问题：给定历史股价、允许多次交易但卖出前不可重复买入，求最大收益，可基于“逢涨即卖”的贪心思想求解；
• 哈夫曼编码：用于无损数据压缩的贪心算法，构建哈夫曼树时每次合并出现频率最低的两个节点，最终可使加权路径长度（编码总长）最小；
• Dijkstra 算法：边权非负图中，每次贪心选取“当前距源点最近且未确定”的顶点来松弛邻边，是典型的贪心式最短路径算法。

此外，《Hello 算法》贪心章节还收录了两道可进一步巩固贪心思想的实战问题：

• 最大容量问题：贪心策略为“每轮向内移动较短板”，将暴力枚举的 $O(n^2)$ 优化为 $O(n)$，见最大容量问题；
• 最大分割乘积问题：先后推导出两条贪心结论——所有 $\ge 4$ 的整数都应继续拆分、最优拆分因子是 $3$，最终借助幂运算在 $O(1)$ 或 $O(\log n)$ 时间内求解，见最大分割乘积问题。

小结与学习路线

回顾全文，贪心算法的知识体系可以压缩为一条主线：它是“每步只做局部最优选择”的最优化策略，效率远高于动态规划，但只有当问题同时满足贪心选择性与最优子结构时才保证全局最优。硬币找零既是理解贪心的最佳入口，也是观察贪心失效的最直观教材——同一问题的动态规划实现（coin_change.py）与之对拍，能清晰展示“局部最优”与“全局最优”之间的鸿沟。

建议的后续学习路径是：先吃透本文的硬币找零反例，再依次阅读仓库贪心章节的分数背包问题、最大容量问题与最大分割乘积问题，配合各语言的贪心目录（如 ja/codes/python/chapter_greedy、ja/codes/cpp/chapter_greedy）逐一运行验证，最后回到贪心小结做整体复盘——届时你会形成“先审题、再定策略、终须证明”的完整贪心解题方法论。