當下就決定，絕不回頭
在暴力法那一階你學會考慮每一種可能，在分治法你學會把問題切成獨立的碎片。貪婪演算法比這兩者都更大膽、也懶得多：它一次一步地建造解，而每一步都按某條簡單規則抓住此刻看起來最好的東西，然後永遠認定這個選擇。不分支、不回溯、不事後猶豫。挑最近的、最便宜的、最早結束的——規則怎麼說就怎麼挑——把它加進答案，繼續往前。整個演算法往往就是一個迴圈、前面加個排序，這正是為什麼一個行得通的貪婪法通常是工具箱裡最快的那一件。
與前幾階的對比正是重點所在。暴力法讓每個選項都活著、為此付出指數代價；你接下來會遇到的動態規劃，會小心保存一張部分答案的表；而貪婪法幾乎把一切都丟掉，只保留它正在建造的那一個答案。當它行得通時，這份莽撞是它的力量；當它不行時，這份莽撞就是它的覆滅。所以這一整階真正的問題，不是怎麼貪婪——那部分很容易——而是貪婪何時被允許，也就是說，何時每一步都抓住局部最好的東西，真的能造出全域最好的解。
一個行得通的小例子，和一個不行的
想像一個小偷，背包能裝 10 公斤，面前是一堆堆的金粉、銀粉和銅粉。金每公斤值 6、銀值 5、銅值 4，每種各有 6 公斤。因為粉末可以分割，貪婪規則既無法抗拒又正確：先拿每公斤最值錢的。用金裝滿 6 公斤（值 36），再用剩下 4 公斤的容量裝銀（值 20），然後停手——共 56。沒有別的裝法贏得了它。這就是分數背包問題，而每一步都抓住最佳的「每公斤價值比」之所以可證明是最佳的，正因為你總能用下一個最好的那堆的一小部分，把剩餘空間填滿。
現在改一個字。面對的不是粉末，而是三根不可分割的金條：A 條重 6 公斤、值 42，B 條重 5 公斤、值 30，C 條重 5 公斤、值 30。貪婪規則「每公斤價值最高者優先」會挑 A 條（比值 7，嚴格高於 B 與 C 的比值 6），裝滿 10 公斤中的 6 公斤；B 與 C 各重 5，所以都塞不進剩下的 4 公斤，貪婪就帶著 42 走人。但最佳答案是同時拿 B 和 C——總重 10、總值 60。貪婪輸得一塌糊塗。這就是0/1 背包，唯一的改變是物品再也不能分割。這個教訓令人不安：同一條規則，用在一個看起來幾乎一模一樣的問題上，就從完美變成大錯。
讓貪婪正確的兩個性質
那麼這兩個背包差在哪？貪婪法可證明為最佳，恰恰當一個問題擁有兩個結構性質。第一個是貪婪選擇性質：存在一個全域最佳解，它包含貪婪規則所做的第一個選擇。你永遠不必為了抵達最佳答案而放棄那個貪婪選擇——某個最佳答案早已與它一致。在分數背包裡，某個最佳裝法早已盡量用上比值最高的那堆，所以貪婪的第一步是安全的。在 0/1 背包裡，沒有這種保證：認定比值最高的那根金條，可能把你鎖在最佳組合之外，正如上面發生的那樣。
第二個是最佳子結構：一旦你鎖定了貪婪選擇，剩下的就是同一個問題的較小實例，而整體的最佳解，就是貪婪選擇加上那個剩餘部分的最佳解。小偷認定 6 公斤金之後，剩下的任務——從銀與銅中最佳地裝滿 4 公斤——不過是一個較小的分數背包。這正是驅動動態規劃的同一個最佳子結構構想，這份重疊並非巧合：兩種範式都攻打那些「最佳解由子問題的最佳解組成」的問題。差別在於，貪婪被允許認定一個子問題、而不去探索其他的，而貪婪選擇性質，正是這麼做的許可證。
兩個性質都得成立。光有最佳子結構不夠——0/1 背包也有最佳子結構（這正是動態規劃解得了它的原因），但它缺了貪婪選擇性質，所以貪婪失敗、而 DP 成功。要記住的口號是：最佳子結構說問題能被分解；貪婪選擇性質說你可以用貪婪的方式分解它，毫無懊悔地拿走局部最好的那一塊。接下來的指南會透過兩種通用證明技術——交換論證與「貪婪總是領先」——把這些性質坐實，它們正是在某個給定問題上證明貪婪選擇性質的真正機械。
局部最好不等於全域最好
每一次貪婪失敗的核心，都有同一道裂縫：局部最佳與全域最佳之間的差別。一條貪婪規則，就其構造而言，會把眼前的選擇最佳化——那個選擇是局部最佳的。但一連串局部最佳的選擇，未必加總成一個全域最佳的整體，因為一個過早的攫取，可能悄悄毒害你後面的選項。0/1 小偷的第一步是局部完美的（最佳的每公斤價值）卻是全域災難性的（它擋住了值 60 的那組配對）。貪婪永遠只能看見一步；這份近視是無害還是致命，全憑問題的結構而定。
greedy(items):
sort items by the greedy rule # the whole "strategy" lives here
answer = empty
for x in items: # one pass, never reconsider
if x is feasible with answer:
answer = answer + x # commit forever, no backtracking
return answer注意這副骨架告訴你「成本對正確性」的什麼。執行時間幾乎總是被排序主宰：一個 O(n log n) 排序加上一趟線性掃描，整體給出 O(n log n)，這正是為什麼一個正確的貪婪法，往往能在同一問題上勝過分治或動態規劃的做法。但若規則是錯的，那份速度就一文不值——一個快速的錯誤答案依然是錯的。並且記住漸進那一階的誠實提醒：O(n log n) 描述的是規模成長，不是每個尺寸都成立的判決。對極小的輸入，排序的開銷可能讓一個笨拙的平方法在實際牆鐘時間上更快；漸進告訴你的是 n 變大時誰贏，而非十個物品時誰贏。
貪婪真正發光之處
別讓這一切的謹慎讓貪婪聽起來脆弱；值得大聲說的是，當貪婪行得通時，它往往是這份工作可能最好的演算法——簡單、快速、精確。這一階其餘部分是它凱旋的巡禮：區間排程，把工作按結束時間排序、抓住每個相容的，可證明為最佳；霍夫曼編碼，反覆合併頻率最低的兩個符號，造出可證明最短的前綴碼；以及著名的最小生成樹演算法，Kruskal 與 Prim 骨子裡都是貪婪、也都正確。這些都不是僥倖的意外——每一個都有貪婪選擇性質，每一個都有一份乾淨的證明來展示它。
對於「貪婪對哪些問題正確？」甚至有個深刻而優美的答案。有些問題共享一種叫擬陣的共同抽象結構，而有一條定理說，貪婪演算法恰恰在那些是擬陣的結構上是最佳的——不多也不少。這是這一階的最後一篇指南，也是貪婪最接近統一律則的東西：它把「我有預感貪婪在這裡行得通」變成「這問題是個擬陣，因此貪婪可證明行得通」。並非每一次貪婪的成功都套得進擬陣的模子（區間排程就是一例，需要它自己的論證），但這仍是一瞥動人的結構，藏在一堆看似零散的巧妙一次性把戲之下。
在你動身往上爬之前，最後一個誠實的提醒。即使一個問題不能用貪婪解，貪婪也很少是無用的——它常常是一個近似的基礎。對許多困難問題，一條貪婪規則給出的答案，保證落在最佳值的某個固定倍數之內，而很後面的某一階會把這講精確。所以光譜是這樣的：有時貪婪恰好最佳（而你證明它），有時它可證明接近（而你界定它），有時它差得離譜（而你放棄它）。知道你身處哪一種情形、並能證明它，正是這一階要教的整套本事。