Greedy Algorithms in Hello Algo: When Local Optima Lead to Global Optimality — and When They Fail

2026-09-07 14:09:10作者：申梦珏Efrain

本篇技术指南聚焦《Hello 算法》仓库中英文版贪心算法章节（en/docs/chapter_greedy/greedy_algorithm.md），以经典的“零钱兑换”问题为主线，系统讲解贪心算法的基本思想、适用条件、正确性判断方法与一般解题流程，并结合仓库内多语言实现源码，帮助读者掌握“何时能用贪心、何时必须改用动态规划”的工程判断力。

导读

贪心算法（Greedy Algorithm）是解决优化问题的一类常见方法。其核心思想朴素而强大：在每一个决策阶段，都选择当前看起来最优的选项——即“贪心地”做出局部最优决策——以期最终得到全局最优解。由于实现简单、运行高效，贪心算法在大量实际问题中都有广泛应用。但它的“局部最优即全局最优”并非总成立：本文将通过零钱兑换问题演示贪心策略的构造过程，通过反例揭示其失效边界，并从仓库源码出发分析其实现细节、复杂度和测试验证方法，最终总结出可复用的三步解题框架。

读完本文，你将能够：用约十行代码实现贪心解法；从时间复杂度层面理解贪心相对动态规划的“数量级优势”；通过反例与数学证明思路判断一个问题是否具备贪心选择性质；并将这套判断流程迁移到分数背包、最大容量等典型贪心问题中。

贪心 vs 动态规划：一个问题的两种解法视角

在进入零钱兑换问题之前，先厘清贪心算法与上一章“动态规划”的关系。两者都常用于求解优化问题，且都依赖“最优子结构”性质，这是它们的共同根基；但在决策方式上截然不同：

动态规划：在做出当前决策时，会综合此前所有阶段产生的决策状态，并借助已求解的过去子问题的解来构造当前子问题的解，是一种“回头看”的全局递推。
贪心算法：不回顾过去的任何决策，而是一路向前地持续做贪心选择。每一步都缩小问题规模，直至整个问题被解决，是一种“只看当下”的前向逼近。

简言之：动态规划把解空间显式展开并通过递推挑选最优路径，而贪心则假设“每一步的最优能自然衔接成全局最优”。这个假设是否成立，正是全文反复检验的核心命题。

通过“零钱兑换”认识贪心：题目与贪心策略

原文档先通过“零钱兑换”这一例题让读者直观理解贪心的工作过程。该题目在仓库的“完全背包问题”章节（unbounded_knapsack_problem.md）中已被正式引入，这里换一种思路重新审视。

!!! question "零钱兑换问题"

给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i - 1]$，目标金额为 $amt$，每种硬币可重复选取。问：**凑出目标金额所需的最少硬币数量是多少？** 若无法凑出目标金额，则返回 $-1$。

贪心策略非常直观：给定目标金额，每次贪心地选择“面值不超过当前剩余金额、且最接近它的那枚硬币”，不断循环直到金额被凑齐。以目标金额 $131$ 、币种 $[1, 5, 10, 20, 50, 100]$ 为例，算法依次选取 $100 \to 20 \to 10 \to 1$ ，剩余金额由 $131 \to 31 \to 11 \to 1 \to 0$ 逐步递减，全过程如下：

图中右侧深色硬币即每次被选中的“不超过剩余金额的最大面值”，灰白硬币表示本轮未命中；左侧标注了每轮扣除后剩余金额的变化路径。这一“选最大可用面值 → 缩小问题 → 再选最大可用面值”的循环，就是贪心算法的典型执行轨迹。

源码实现：约十行代码的简洁方案

原文档中的示例代码通过 MkDocs 的 src 指令动态注入仓库源码。此处给出仓库内 Go 与 Python 两版核心实现的完整代码，便于逐行对照。

Go 版本见 codes/go/chapter_greedy/coin_change_greedy.go：

/* 零钱兑换：贪心 */
func coinChangeGreedy(coins []int, amt int) int {
	// 假设 coins 列表有序
	i := len(coins) - 1
	count := 0
	// 循环进行贪心选择，直到无剩余金额
	for amt > 0 {
		// 找到小于且最接近剩余金额的硬币
		for i > 0 && coins[i] > amt {
			i--
		}
		// 选择 coins[i]
		amt -= coins[i]
		count++
	}
	// 若未找到可行方案，则返回 -1
	if amt != 0 {
		return -1
	}
	return count
}

Python 版本见 codes/python/chapter_greedy/coin_change_greedy.py：

def coin_change_greedy(coins: list[int], amt: int) -> int:
    """零钱兑换：贪心"""
    # 假设 coins 列表有序
    i = len(coins) - 1
    count = 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 列表有序”：算法从索引 i = len(coins) - 1（最大面值）出发，本质假设币种已按面值升序排列。若调用方传入无序数组，结果不可预期——这是使用该函数的前提条件。
内层指针只减不增：由于剩余金额在每轮扣除后只会变小，能“装下”的最大面值只会向左移动，因此索引 i 单调左移即可覆盖所有贪心选择，无需回退扫描。
退出判断：外层 for amt > 0 循环假定 coins[0]（最小币种）足以兜底任意金额；if amt != 0 { return -1 } 一行用于防御“无法凑出”的退化场景（例如最小币种为 0 或传入空集时防止死循环）。

正如原文档感叹的那样：So clean! ——贪心算法仅用约十行代码便回答了这道看似需要铺开状态表的优化问题。

贪心算法的优点与局限性

优点：直接、简单、高效

贪心算法不仅操作直接、实现简单，而且通常效率很高。在以上代码中，记硬币最小面值为 $\min(coins)$ ，则每轮至少消耗 $\min(coins)$ 金额，贪心选择最多循环 $amt / \min(coins)$ 次，时间复杂度为

O(amt / \min(coins))

而仓库中给出的动态规划解法（完整实现见 codes/go/chapter_dynamic_programming/coin_change.go）需要枚举币种数与金额两个维度，时间复杂度为 $O(n \times amt)$ 。当币种种类数 $n$ 远大于最小面值对金额的分摊速度时，贪心的时间复杂度可比动态规划低一个数量级——这正是贪心在可解场景下极具吸引力的根本原因。

局限性：硬币面值组合可能让贪心失效

然而，对于某些硬币面值组合，贪心算法并不能找到最优解。原文档给出了一个正例与两个反例：

正例 $c o i n s = [1, 5, 10, 20, 50, 100]$ ：在该组合下，对任意 $a m t$ ，贪心都能找到最优解——这是货币体系“面值逐级可整除”特性的典型体现。
反例 $c o i n s = [1, 20, 50]$ ， $a m t = 60$ ：贪心只能得到 $50 + 1 \times 10$ 的兑换组合，共 11 枚硬币；而动态规划可以给出 $20 + 20 + 20$ ，仅需 3 枚硬币。
反例 $c o i n s = [1, 49, 50]$ ， $a m t = 98$ ：贪心只能得到 $50 + 1 \times 48$ ，共 49 枚硬币；而动态规划的最优解 $49 + 49$ 仅需 2 枚硬币。

两个反例的失效机理一致：贪心在第一轮“锁死”了面值 $50$ ，导致剩余金额落入“必须用大量 $1$ 补齐”的低效区间；而真正的最优方案恰恰需要放弃当前局部最优（ $50$ ），为后续组合让路。该对比在图示中一目了然：

上表逐行对比了不同币种组合与目标金额下，贪心求得的“局部最优解”与动态规划求得的“全局最优解”：左列贪心结果大量堆叠最小面值（11 枚、49 枚），右列动态规划则以同面值硬币的组合达成最少数量（3 枚、2 枚）。结论是：对于零钱兑换问题，贪心无法保证全局最优，甚至可能产出极差的解，此时应改用动态规划。

一般适用情形

原文档将贪心算法的适用情况概括为两类：

可以保证找到最优解：此时贪心往往是最优选择，因为它通常比回溯、动态规划更高效——直接用即可；
可以找到近似最优解：很多复杂问题寻找全局最优极难，能以较高效率得到“次优解”也是可接受的良好结果——贪心在此场景中依然可用。

这一“二分适用性”意味着：工程实践中贪心并不需要永远正确，只要能在成本约束内给出足够好的答案，就具备实用价值。

贪心算法的两大特性：何时能保证最优？

那么，什么样的问题适合用贪心？或者说，贪心在什么条件下能保证找到最优解？ 与动态规划相比，贪心的使用条件更苛刻，其成立依赖问题的两个性质：

贪心选择性质（Greedy Choice Property）：只有当“局部最优选择”始终能导向“全局最优解”时，贪心算法才能保证正确。这是贪心区别于动态规划的决定性条件——动态规划即便局部选择不是最优，也能通过状态转移在全局范围内兜底纠偏；贪心没有纠偏机制。
最优子结构（Optimal Substructure）：原问题的最优解包含子问题的最优解。该性质已在“动态规划”章节（intro_to_dynamic_programming.md）详述，此处不展开。值得注意的是，部分问题的最优子结构并不显眼，却依然可被贪心解决。

两大性质中，最优子结构容易验证，贪心选择性质才是真正的难点。原文档指出一个耐人寻味的事实：在零钱兑换问题中，人们可以轻松举出反例证伪贪心选择性质，但若要正面证实“何种币种组合贪心恒最优”，往往只能依赖直觉或例子给出模棱两可的答案，难以给出严谨的数学刻画。

一个来自学术界的精确回答

针对上述困境，原文档引用了一篇关键论文：

!!! quote

有一篇论文给出了一个 $O(n^3)$ 时间复杂度的算法，用于判断一个硬币组合能否使用贪心算法找出任意金额的最优解。

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

该文献表明：“哪种币值体系对贪心‘友好’”在计算上是可在多项式时间内判定的——从实践层面看，若你对某个币种集合心存疑虑，这类判定算法比漫无目的地构造反例更可靠。

贪心算法解题三步法

原文档将贪心问题的解决流程归纳为三步，这也是进行贪心题单训练时值得固化的方法论：

问题分析（Problem Analysis）：梳理并理解问题特性，包括状态定义、优化目标与约束条件。这一步与回溯、动态规划的建模步骤一致，是三类算法共有的地基。
确定贪心策略（Determine the Greedy Strategy）：明确每一步“如何贪”。一条合格的贪心策略必须能让问题规模逐步缩减，直至完全解决——例如零钱兑换中“选不超过剩余金额的最大面值”，每次扣款都严格减少 $a m t$ 。
正确性证明（Correctness Proof）：通常需要证明问题同时具备贪心选择性质与最优子结构，常用数学工具为数学归纳法与反证法。

三步之中，确定贪心策略是核心，却往往最不易实施。原文档点出两大现实障碍：

不同问题的贪心策略差异较大：多数问题的贪心策略较为浅显，通过大致思考与尝试即可得出；但对复杂问题，贪心策略可能十分隐蔽，非常考验解题经验与算法功底。
某些贪心策略极具迷惑性：你可能满怀信心地设计好策略、写完代码并提交，却在若干测试用例上败下阵来。原因在于设计的策略只是“部分正确”——上文零钱兑换的 $[1, 20, 50]$ 、 $[1, 49, 50]$ 两例就是现成的“翻车现场”。

正确性证明的两条路线

为保证正确性，应当对贪心策略给出严谨的数学证明，通常使用反证法或数学归纳法：

反证法：假设存在某个违背贪心选择的最优解，通过交换论证证明该最优解可以被替换为包含贪心选择的等价或更优解，导出矛盾，从而说明“贪心选择必然出现在某个最优解中”。
数学归纳法：证明“在贪心做出第 $k$ 步选择后，剩余子问题依然与原问题同构，且贪心前 $k$ 步的解可延拓为全局最优解”，从而由归纳奠基递推到完整问题。

然而正确性证明同样可能无路可走。原文档给出的务实兜底是：若没有清晰思路，通常面向测试用例进行调试，构造典型反例与随机数据，一步步修改并重新验证贪心策略。这也与仓库工程实践相呼应——见下文测试小节。

反例驱动的策略迭代：仓库中的可复现实验

仓库为该算法提供了现成的“反例试验台”。Go 版单测 codes/go/chapter_greedy/coin_change_greedy_test.go 以及 Python 驱动代码（见 codes/python/chapter_greedy/coin_change_greedy.py 的 Driver Code）恰好按“正例 → 反例”的顺序组织：

币种 [1, 5, 10, 20, 50, 100]、目标 $186$ ：贪心输出最优硬币数；
币种 [1, 20, 50]、目标 $60$ ：贪心输出非最优结果，注释标出“实际上需要的最少数量为 3，即 20 + 20 + 20”；
币种 [1, 49, 50]、目标 $98$ ：贪心输出非最优结果，注释标出“实际上需要的最少数量为 2，即 49 + 49”。

这说明测试用例驱动的“证伪—修正”循环是检验贪心策略的有效手段：先跑通快乐路径，再用构造性反例试探策略边界。仓库内同章节各语言的实现结构一致（如 C++ 版见 codes/cpp/chapter_greedy/coin_change_greedy.cpp），便于跨语言对照同一算法逻辑。

典型贪心问题与仓库内的配套实现

贪心算法常被用于求解满足贪心选择性质与最优子结构的优化问题。原文档列举的典型问题中，分数背包、最大容量、最大切分乘积三类问题在仓库的贪心章节内均有完整可运行实现，可作为学习贪心策略设计的配套案例：

硬币找零问题：在特定硬币组合下，贪心总能得到最优解（本节主案例）。
分数背包问题：给定一组物品与载重量，目标是使总重量不超载且总价值最大。若每步都选择性价比（价值 / 重量）最高的物品，贪心在部分情况下可获最优解——完整实现见 fractional_knapsack_problem.md 与代码 codes/go/chapter_greedy/fractional_knapsack.go。
最大容量问题：以短板决定容积的容器问题，双指针贪心能保证最优——见 max_capacity_problem.md 与 codes/go/chapter_greedy/max_capacity.go。
最大切分乘积问题：将整数切分为若干正整数使乘积最大，贪心按因子 $3$ 切分——见 max_product_cutting_problem.md 与 codes/go/chapter_greedy/max_product_cutting.go。
区间调度问题：任务各占一段区间，目标是完成尽量多的任务；每次都选择“结束时间最早”的任务即为最优贪心策略。
股票买卖问题：给定历史价格可多次买卖，但持有期间不能再买入，目标是最大化总利润。
霍夫曼编码：面向无损数据压缩的贪心算法，通过反复合并当前频率最低的两个节点构造霍夫曼树，使带权路径长度（编码总长度）最小。
Dijkstra 算法：在边权非负的图中，求解给定源点到其余各顶点最短路径的贪心算法。

这些问题的共性在于：都能找到一种“每步缩减问题规模”的局部准则。建议按本章总结的三步法，先为上述题目口述贪心策略，再尝试反证或归纳，最后回到代码层面验证——完整的题目训练清单见 summary.md 与 exercises.md。

小结：把“贪心”当工具而非信仰

回顾全文，贪心算法留给工程实践者最重要的心智模型有三层：

效率红利巨大但前提苛刻： $O(amt / \min(coins))$ 级别的循环开销远比 $O(n \times amt)$ 的 DP 优雅，但这建立在“局部最优 = 全局最优”的强假设之上，币种组合一变就可能坍塌为 11 枚、49 枚硬币的糟糕解。
判断优先于证明，测试优先于自信：最优子结构好验证，贪心选择性质难证实；遇到“部分正确”的迷惑性策略，及时退回到反例构造与单测调试，而非凭直觉硬撑。
同一问题可以有算法谱系：零钱兑换既是完全背包问题（DP 视角），又是贪心算法的入门例题（贪心视角），还是回溯搜索的适用对象。仓库将同一问题在 chapter_dynamic_programming 与 chapter_greedy 两章中分别呈现，正是为了训练“按需选用算法”的判别力——贪心是通往最优解的一条捷径，但只有当你验证过这条路确实通向终点时，才值得把身家押在它上面。