贪心 · 什么时候是对的

贪心算法写起来几乎没有代码量：排个序，从头扫一遍，能拿就拿。Kruskal 按边权从小到大取，Huffman 每次合并权重最小的两点，区间图着色 按开始时间逐个分房——三处的骨架是同一句话。难的从来不是写出来，而是判断这句话对不对：同样自然的另一条规则，在同一道题上就能差出一大截。

本系列答的就是这一个问题。第一页给出交换论证这套模板，并把它做成可以单步执行的东西：取一个最优解，找到它与贪心解的第一处分歧，把那一处换成贪心的选择，看它是否仍然可行；换错了规则，断裂点会当场出现在某一步上。第二页把判据抽象成结构——独立系统满足交换性质即 matroid，Rado–Edmonds 定理说这恰好等价于「贪心对一切权函数都最优」，Kruskal 由此成为定理的一个推论。第三页回到工程：带截止时间的单机调度、按利润排的作业排程，以及一组看起来该贪心却不能贪心的题——0-1 背包与非规范币值下的找零，都能在 lab 里看到贪心解与最优解的具体差值。

三种判据的分工

三页不是三种口味，是同一件事的三个粒度。交换论证针对一道具体的题，逐题写、逐题证，代价是每换一道题就要重来一遍；matroid 针对一族题，一旦验出结构，一切权函数上的最优性一并成立，代价是许多真实问题并不落在这个结构里；反例针对判断本身，它不证明什么，但能在几秒内否掉一个猜想。工程上的次序通常是倒过来的：先找反例，找不到再想论证，论证反复出现同一套骨架时才去看结构。

贪心失败之后

一条贪心规则被反例否掉，不等于这道题无解，只等于「一次决策不能只看眼前」。此时的标准退路是把被丢掉的那部分信息记进状态，即动态规划：0-1 背包、带权 interval scheduling、任意币值的找零，三者都是这样从贪心退回 DP 的。分界线在第三页给成一张表。 exchange argument

交换论证：贪心凭什么最优

interval scheduling 上四条同样自然的选取规则，只有 earliest finish time 撑得起证明。本页把「取最优解、找第一处分歧、换成贪心的选择、归纳」做成可执行的四步，并给出另外三条规则各自断裂的位置与反例。

Rado–Edmonds

matroid：贪心最优的充要条件

独立系统满足交换性质即 matroid。Rado–Edmonds 定理说这恰好等价于「按权重降序的贪心对一切权函数都给出最优解」，Kruskal 由此成为推论；两个只差一条公理的系统则当场崩掉。

EDF · job sequencing

调度与背包：贪心的边界

三组落地问题：单机调度用相邻交换证明 EDF 最优，job sequencing 靠并查集找空位且最优性由 matroid 保证，0-1 背包与非规范币值找零则给出能跑出差值的反例。末节是一张判断表。

相关链接

• 最小生成树 · Prim 与 Kruskal 本站 Kruskal 的正确性在那页由 cut theorem 给出；本系列第二页给出另一条路——它是 graphic matroid 上 Rado–Edmonds 定理的直接推论。
• 动手建树 · 每次合并两个最小 本站 最经典的交换论证实例：任一最优前缀码都能通过交换两个叶子改造成 Huffman 的形状。
• 区间图 · 贪心直接最优 本站 同一批区间的另一个问题：不是选最多的互不相交区间，而是把全部区间分进最少的房间。
• 动态规划 · 背包问题九讲 本站 贪心被反例否掉之后的标准退路；0-1 背包与找零都在那里得到多项式解。
• 并查集 · disjoint set 本站 两处底座：graphic matroid 的 independence oracle，与 job sequencing 里「找不晚于截止时间的最大空槽」。
• Edmonds (1971) — Matroids and the greedy algorithm doi.org Rado–Edmonds 定理的标准出处：贪心对一切权函数最优当且仅当独立系统是 matroid。