走過四篇之後，那個誠實的問題
到目前為止，你已看過貪婪四度成功。在區間排程中，「最早結束時間」規則藉由貪婪保持領先被證明為最佳；在霍夫曼編碼中，合併兩個最罕見符號的做法則靠交換論證獲得正當性。兩個證明都倚靠第一篇指南就立下的同兩根支柱：貪婪選擇性質（存在某個最佳解與第一個貪婪選擇一致）與最佳子結構（做完那個選擇後剩下的，是一個同類型的較小問題）。兩者皆成立時，貪婪有效；當我們能證明它們時，事情就完成了。
但四場勝利不是一條定理，而「看起來局部最佳」從來就不是證明——這道警告貫穿了本階每一篇指南。所以還剩兩個誠實的問題。第一：有沒有一個單一的結構能「解釋」為什麼貪婪正確，而不必每次都重新湊一個臨時論證？第二：當貪婪是錯的時，我們怎麼知道，而又該改做什麼？本指南回答這兩者。那個結構有個名字——擬陣——而那個典型的失敗也有個名字：0/1 背包問題。
擬陣：許多貪婪證明背後的單一抽象
擬陣是一份刻意精簡的記帳。你從一個有限的元素基底集開始，並宣告它的某些子集為獨立——也就是「被允許的」或「無衝突的」。關鍵在於這個獨立集族並非任意；它必須遵守恰好兩條規則。遺傳規則：獨立集的每個子集都獨立（拿掉一個元素，你仍被允許）。交換性質：若 A 與 B 皆獨立，且 A 的元素比 B 少，則 B 中存在某個元素能加入 A，並使 A 保持獨立。第二條規則就是整部引擎，所以請牢牢記住它。
你在哪裡見過這完全相同的東西？在生成樹的故事裡。取一個圖；若一組邊不含環（也就是一片森林），就稱它「獨立」。從森林拿掉一條邊，它仍是森林——這是遺傳。而若森林 A 的邊比森林 B 少，則 A 有較多的連通分量，所以 B 中必有某條邊跨接在 A 的兩塊之間而不閉合成環——這就是交換性質在野外活生生地運作。這個特定的擬陣稱為圖擬陣，而它正是 Kruskal 演算法為何正確的原因。
貪婪走下懸崖之處：0/1 背包問題
現在是那個警世故事。你有一個容量 W 的背包與一堆物品，每件有重量與價值，你想要塞得進去的最有價值的一批。在分數版本——你可以拿一件物品的任意比例——貪婪是完美的：依每單位重量的價值（「密度」）排序，先倒入最密的，最後再切下恰好足量的下一件來填滿背包。分數背包問題其實是一個帶擬陣風味的成功：貪婪選擇性質成立，因為最密的那一單位價值永遠值得最先抓取。
0/1 背包問題只改了一個字——每件物品必須整件取走或完全不取——而同樣的貪婪規則就崩潰了。這裡有個小小的追蹤。容量 W = 10。物品 A：重量 6、價值 7（密度約 1.17）。物品 B：重量 5、價值 5（密度 1.0）。物品 C：重量 5、價值 5（密度 1.0）。最密優先的貪婪抓了 A，接著剩下 4 的容量，B 與 C 都塞不進，總價值為 7。但 B 加 C 合起來恰重 10、值 10。貪婪走下了懸崖：它得到 7，而其實有 10 可拿，再多的「可是 A 看起來最好」也救不了它。
是什麼壞了？最佳子結構還活著，但貪婪選擇性質死了：不存在任何包含第一個貪婪選擇（A）的最佳解。取了 A，就永遠斷送了 B+C 的配對，而背包的「容量是一個把各物品耦合在一起的全域限制」——一個孤立看來最佳的選擇，毒害了後續的選擇。那種耦合，正是擬陣交換性質所禁止、而 0/1 背包問題所恣意違犯的。這個教訓正是本階不斷重複的：貪婪不是萬用方法，它是「一場只在問題具備正確結構時才划算的賭局」，而「局部最佳」是一個有待證明的假設，永遠不是證明。
當貪婪是錯的時，該轉向什麼
貪婪失敗不是路的盡頭——它是一塊路標。最常見的下一站是動態規劃，它保留存活的那根支柱（最佳子結構），卻不再信任單一的貪婪選擇；取而代之，它「嘗試每個選擇並記住最好的」。用動態規劃解 0/1 背包會建一張以（已考慮的物品、已用的容量）為座標的表，並在每件物品處問「取它好，還是不取好？」，同時把兩種可能性都帶往後續。在我們那個小例子上，它會發現 B+C = 10，因為它在檢查替代方案之前絕不對 A 下承諾。代價很誠實：那張表是 O(n * W) 的時間與空間，當 W 不大時很有效率，但它「並非」真正對輸入位元長度多項式——0/1 背包問題是 NP 困難的，沒有已知方法能對所有輸入都快。
有時連動態規劃都太慢，因為問題的核心就是 NP 困難的，這時貪婪以一個更謙卑的角色捲土重來——不是作為精確方法，而是作為快速的近似。貪婪集合覆蓋演算法反覆抓取覆蓋最多尚未被覆蓋元素的集合；它找不到最佳解，但可被證明落在最佳解的約 ln(n) 倍之內。要把這種保證的意思說精確：近似比是一個「最壞情況」界限，一個承諾答案永不差於那個倍數乘以最佳值——而非對典型情況的宣稱，在典型情況下它往往好得多。
整個階段，一口氣說完
退一步，這五篇指南構成一道弧。第一篇點名了那兩根支柱；第二、三篇給了你兩套核心證明技巧（貪婪保持領先，與交換論證）；第四篇讓兩者在一個真實的編碼器裡同台運作。本指南補上它們底下缺失的理論——擬陣——以及那條誠實的界線：貪婪正確，恰恰是在問題所允許的解具有足夠結構之時（一個擬陣，或一個交換證明）；而當一個全域限制把各選擇耦合起來時，它就是錯的，有時錯得驚人，正如 0/1 背包問題。
帶走的是那個習慣，不是那句口號。「取局部最佳的選項」是個誘人的反射動作，但本階一切的價值在於「懷疑它的紀律」——在你把一個要緊的問題託付給某個貪婪演算法之前，先索求一個證明，或一個反例。那種紀律，正是下一階動態規劃會回報的心態，在那裡，記住並重新斟酌，取代了單一而不可逆的貪婪承諾。