贪心算法

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

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

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

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

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

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

同一思路还有一个"超前论证"（greedy stays ahead）版本：把贪心解与任意可行解按结束时间并排比较，可以归纳证明——贪心解里第 $k$ 个活动的结束时刻，永远不晚于对方第 $k$ 个。一旦超前成立，贪心就能塞进不少于对方的活动数。交换论证关心"能不能局部替换"，超前论证关心"全程进度会不会落后"；两者常可互换，但在教学里后者往往更直观——它把正确性说成一场赛跑，而不是一场置换。

活动选择还能推广到区间着色：给一批区间染色，使相交区间颜色不同，最少色数等于最大重叠数。策略是按开始时间扫描，把每个区间染成此刻空闲的最小编号色。这里贪心的对象从"选哪些区间"变成了"给每个区间什么颜色"，但精神仍是局部决策、永不回退。它提醒我们：同一家族的区间问题，目标函数一变，贪心策略的"刻度"也要跟着换。

主要应用领域#

调度与分配#

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

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

图算法中的贪心#

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

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

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

数据压缩#

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

正确性可以靠"兄弟性质"看清：在任意最优前缀码树里，频率最低的两个符号一定可以做成兄弟叶节点；把它们合并成一个超符号后，子问题仍是同构的前缀码问题。于是每一步"合并最轻的两个"都不会堵死最优解——这是交换论证在编码树上的具体形态。与活动选择不同，这里稀缺的不是时间轴上的空档，而是码字的前缀空间：浅层比特被高频符号优先占用，深层比特留给低频符号，平均码长被压到信息论下界附近。工程上它还常与块划分、自适应频率估计联用，但核心的一步一步合并，始终是那个贪心核。

集合覆盖的近似比：若坚持精确最优，集合覆盖是 NP-hard；若允许近似，经典贪心——每次选覆盖尚未覆盖元素最多的集合——保证近似比不超过 $H_n \approx \ln n + 1$。证明用单位收费法：每个元素按其被覆盖那一刻的"边际价格"付账，再与最优解的总账对照。这类结果把贪心从"要么精确、要么放弃"里解救出来——在组合优化里，贪心常常是有担保的近似算法，而不只是启发式。

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

找零问题：不一定有效#

用 [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. 如果贪心在所有尝试上都失败，转向动态规划

实操时还有几条常被教科书略写、却能省大量弯路的习惯。第一，先固定排序键，再谈正确性：许多贪心的真正发明，是找到那个让交换论证成立的排序（结束时间、密度、截止期），而不是写出"每次取最大"四个字。第二，反例要造得小而毒：三五个元素就够打穿错误策略；若你只能用几十个元素才凑出反例，多半还没抓住失效机制。第三，把"精确最优 / 有界近似 / 仅启发式"三档分开说：同一问题在不同约束下可能分属三档——分数背包是精确，集合覆盖贪心是 $\ln n$ 近似，TSP 近邻法则多半只是启发式。第四，线上版本要单独论证：离线活动选择的正确性，推不到"活动一个个到达、不可预知"的在线场景；在线贪心往往要靠竞争比分析，那是另一套账本。

若交换论证一时写不出，不妨先写"假设存在反例，取字典序最小的那个"——最小反例法常能把论证逼到只剩一个局部置换。拟阵检验则是另一条捷径：可行解族若满足遗传与增广，按权排序取入即最优，连交换过程都可以省略。两条路都走不通时，再老老实实建 DP 状态，通常比继续硬凑贪心更省时间。

跨域连接#

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

参考文献#

• 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章）