贪心算法

1956 年，年轻的 Edsger Dijkstra 在为阿姆斯特丹数学中心编写程序时，想到了一个简洁到让人惊叹的主意：每次都走目前看起来最近的路，就这样，不回头。

这就是贪心算法的核心精神：在每一步，做出局部最优的选择，从不回溯。它不考虑未来，不担心后悔，只管眼前最好。

令人意外的是，这种"鲁莽"的策略在许多重要问题上给出了全局最优解——这不是运气，而是这类问题具有深刻的数学结构。

破除误解：贪心不等于次优#

很多人第一次学贪心算法时，直觉上认为它是一种"凑合"的策略——动态规划才是真正的最优解法，贪心不过是个近似。

这是误解。对于具有特定结构的问题，贪心给出精确的全局最优解，而且往往比动态规划更快、更简单。问题的关键不是"用不用贪心"，而是"这个问题适不适合贪心"。

区分的标准有两个数学条件：

1. 贪心选择性（Greedy Choice Property）：局部最优选择能导出全局最优解——每一步的贪心决策不会破坏未来的最优性。
2. 最优子结构（Optimal Substructure）：问题的最优解包含子问题的最优解。

同时具备这两个条件，贪心算法就能给出精确最优解。只有最优子结构而没有贪心选择性时，只能用动态规划。

经典案例：活动选择问题#

这是贪心算法最干净的入门案例，由 Cormen 等人在 CLRS 教材中作为范例详细讲解。

问题：有 $n$ 个活动，每个活动 $i$ 有开始时间 $s_i$ 和结束时间 $f_i$。一个人一次只能参加一个活动（时间不重叠），请选出最多的活动数量。

贪心策略：始终选择结束时间最早的、与已选活动不冲突的下一个活动。

直觉：选结束最早的活动，就给后续活动留出最多时间——这是"占用资源最少"的选择。

活动列表（已按结束时间排序）：
活动 A: [1, 4]
活动 B: [3, 5]
活动 C: [0, 6]
活动 D: [5, 7]
活动 E: [3, 9]
活动 F: [6, 10]

贪心过程： 选 A [1,4] → 选 D [5,7] → 选 F [6,10]（与 D 冲突，跳过） 实际最优：A + D = 2 个活动 ```

时间复杂度：先按结束时间排序 $O(n \log n)$，然后线性扫描 $O(n)$，总计 $O(n \log n)$。

为什么贪心在这里是对的？（交换论证，Exchange Argument）

设最优解 $S^*$ 不包含第一个结束时间最早的活动 $a_1$，则 $S^*$ 中第一个活动 $a_k$ 的结束时间 $f_k \geq f_1$。将 $a_k$ 替换为 $a_1$，活动数量不减少，且替换后结束更早——不比 $S^*$ 差。由此归纳，每步贪心都安全。

为什么偏偏是"结束最早"？ 几个同样自然的策略都会失败，对比之下才能看清正确策略抓住了什么：

• 选开始最早的：一个 0 点开始、贯穿全天的活动会第一个被选中，挤掉全天本可容纳的一串短活动。
• 选时长最短的：短活动若恰好横跨两个长空档之间的接缝，选它就同时废掉了两侧各一个本可容纳的活动。
• 选冲突最少的：冲突少不代表占用资源的"位置"好，同样可以构造出它错过最优解的例子。

"结束最早"之所以安全，是因为这个问题里真正稀缺的资源是剩余可用时间——每选一个活动，未来还能用的就是从它结束时刻起算的时间。结束最早等价于"给未来留下最多资源"，这正是交换论证能成立的结构性原因。

主要应用领域#

调度与分配#

带截止日期的工作调度：每个工作有价值和截止日期，贪心策略是按价值降序处理，用不相交集（Union-Find）高效找到最晚可用时间槽。

最优装载：集装箱问题——按重量从小到大贪心选，直到超重。对于整数重量、连续装载问题，贪心给出最优解；对背包问题（可以不完整装），贪心给出分数背包的精确最优解，但对0-1背包无效。

图算法中的贪心#

Kruskal 最小生成树：每次选权重最小的、不成环的边。这是贪心的直接应用，正确性由拟阵理论（matroid theory）保证。

Prim 最小生成树：从一个节点出发，每次贪心地选一条最小权重边，将新节点加入已访问集合。

Dijkstra 最短路径：每次从未访问的节点中选距离源点最近的，是贪心思想在图上的精彩应用。

数据压缩#

霍夫曼编码（Huffman Coding）：每次合并频率最低的两棵树。这是贪心给出最优前缀码的经典案例。

贪心的失效：陷阱与边界#

找零问题：不一定有效#

用 [1, 3, 4] 分值的硬币凑出 6 元，贪心选最大：$4 + 1 + 1 = 3$ 枚；但最优是 $3 + 3 = 2$ 枚。

有意思的是，美元币制 [1, 5, 10, 25, 50, 100] 用贪心却总是最优——这类币制称为正则币制（Canonical Coin System）。差别不在运气：正则性是一个可以机械检验的性质。Kozen 和 Zaks（1994）证明：若贪心在某个币制上会失败，最小的失败金额一定小于"最大面值与次大面值之和"——检验一个币制只需在这个有限区间内逐一枚举。Pearson（2005）进一步给出多项式时间的判定算法，直接算出"最可疑的候选反例"逐一验证，无需遍历整个区间。

对任意币制求最优找零，必须用动态规划：设 $f(v)$ 为凑出金额 $v$ 的最少硬币数，则 $f(v) = 1 + \min_{c \le v} f(v - c)$。状态是"还剩多少钱"，与钱怎么花掉无关——这正是最优子结构成立而贪心选择性不成立的典型形态。

0-1 背包：贪心失败#

每次选"价值密度最高"的物品，对于连续背包（可切割物品）是精确最优的；但对于不可切割的 0-1 背包，贪心会失败，因为问题缺少贪心选择性。

旅行商问题：NP-hard#

"每次去最近的未访问城市"的贪心策略给出的路径，可能比最优解长出数倍。TSP 问题没有已知的多项式时间精确算法。

贪心与动态规划的分界线#

把贪心和动态规划放在一起看，它们处理的是同一家族的问题，分界线在"选择之后，剩下的子问题长什么样"。

分数背包可以贪心、0-1 背包不行，原因可以讲得十分具体。分数背包里物品可以切割：拿走密度最高物品的一部分后，剩余问题仍是同构的背包问题，只是容量变小——任何替代方案都能用"密度更高的那份"换出"密度更低的那份"，交换论证成立。0-1 背包里物品不可分割：选走密度最高的物品可能刚好占掉一段尴尬的容量，使另外两件组合装不下——选择产生了机会成本，而贪心看不见它。动态规划的应对是把"剩余容量"纳入状态：$f(i, c)$ 表示前 $i$ 件物品、容量 $c$ 下的最优值，枚举"选 / 不选第 $i$ 件"两种未来再取优。状态空间因此从"一个指针"膨胀成 $n \times C$ 的表——这就是为"贪心在此会错"所付的代价。

加权活动选择是同一个故事。不加权时"选结束最早的"之所以对，是因为每个活动价值相同，比的是数量；一旦活动带权，早结束的活动可能价值极低，局部最优与全局最优脱钩，标准解法变成按结束时间排序后做动态规划。规律是：贪心选择性本质上是"存在一个安全的交换"，而交换是否安全，取决于目标函数对选择的敏感方式——收益同质化时交换安全，异质化时往往需要动态规划把未来的账算清楚。

贪心算法的数学基础：拟阵理论#

为什么有些问题上贪心是对的，而另一些问题上不行？这不是偶然，背后有深刻的代数结构——拟阵（Matroid）。

拟阵是一种抽象数学结构，满足交换性、遗传性和增广性公理。可以证明：在拟阵上，贪心算法（按权重从大到小依次加入独立集）给出最大权独立集。

三条公理的直觉不妨一看。遗传性：独立集的子集仍独立（无环边集删掉一条边仍无环）。增广性（交换性）：若 $A$、$B$ 独立且 $|A| < |B|$，则必能从 $B$ 中找一个元素加入 $A$ 使其仍独立（两棵大小不同的森林，大森林里必有一条边连接小森林内部的两个分量）。增广性正是"交换论证"的公理化：它保证任何局部选择都不会把未来的最优解堵死——前面跨域连接里说的"机会成本为零"，落在纸面上就是这一条。

图的无环子图、线性独立向量集等都是拟阵。这解释了为什么最小生成树算法（Kruskal/Prim）和活动选择等问题上贪心是精确的。

这一理论由 Jack Edmonds 在 1971 年论文"Matroids and the Greedy Algorithm"中建立，是算法理论的里程碑。

设计贪心算法的方法论#

1. 先尝试最自然的贪心策略（最大/最小/最早/最晚）
2. 用小例子验证：构造反例，如果找得到反例，该策略不适用
3. 用交换论证或截断论证证明正确性
4. 如果贪心在所有尝试上都失败，转向动态规划

跨域连接#

• 线性代数：拟阵把"线性无关"抽象成三条公理，而图的无环边集与向量的线性无关集都满足它们。可以证明：在拟阵上按权重排序依次取入独立集，贪心给出最大权独立集。这才是最小生成树上贪心成立的真正理由，也给出一条检验路径——遇到新问题先问它的可行解族是不是拟阵，比一个个试反例更快。
• 机会成本：贪心失效的机制可以用一句经济学的话讲清——它忽略了所选方案占用共享资源带来的机会成本。背包里选走密度最高的那件就占掉容量，使另外两件一起装不下；而拟阵的交换性质保证任何选择都不会封死后续可行性，机会成本恰为零。能不能贪心，等价于问这个成本是不是零。
• 玻璃与陶瓷：熔体冷却时每个原子就近落到当下能量最低的位置，这是彻底的贪心，结果就是玻璃——一个远离全局最低能量的无序态。同一成分、冷速不同，分别得到玻璃或晶体，这是贪心失效最实在的实物证据。缓慢降温之所以能得到晶体，正是因为它给了系统回退与重排的机会。
• 公平的健康优先级设定：把干预按每单位成本带来的健康收益排序、依次纳入直到预算耗尽，正是分数背包的贪心，在项目可任意缩放时精确最优。但医院、设备与培训项目大多不可分割，排序法给出的只是上界，会系统性高估既定预算能买到的健康。再加上覆盖弱势人群这类公平约束，可行解族就不再是拟阵。
• 最小生成树：这是拟阵条件成立的样板——每次选最小的不成环边，切割引理保证它属于某棵最优树。证明手法值得单独记住：假设最优解不含这条边，把它换进去、把跨越同一切割的更重边换出来，总权不增，与最优性矛盾。凡能构造出这种交换的问题，贪心就有戏。

参考文献#

• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第16章 Greedy Algorithms）
• Edmonds, J. "Matroids and the Greedy Algorithm." Mathematical Programming 1, 1971.
• Kozen, D. & Zaks, S. "Optimal Bounds for the Change-Making Problem." Theoretical Computer Science 123(2), 1994.
• Pearson, D. "A Polynomial-Time Algorithm for the Change-Making Problem." Operations Research Letters 33(3), 2005.
• Kleinberg, J. & Tardos, É. Algorithm Design. Pearson, 2005. （第4章）