貪心每次做當下看起來最好的選擇，並且不再反悔。它比動態規劃快，也比動態規劃容易寫錯：很多問題「看起來能貪」其實不能。本篇用交換論證說明什麼時候貪心是對的，並把活動選擇、分數背包、霍夫曼編碼做成可手算的完整例子。
相關教材：Dynamic_Programming_Teaching_Materials.md（不能貪的時候改走 DP）、10_SetCover_Teaching_Materials.tex（貪心近似）、Graph_Algorithms_Complete_Teaching_Materials.tex（Dijkstra、Prim、Kruskal）、Heap_Priority_Queue_Teaching_Materials.md（霍夫曼要用優先佇列）。
目錄
1. 貪心在做什麼
一個最佳解可以想成一連串選擇。貪心策略：
- 訂一個局部排序規則（最早結束、單位價值最高、頻率最小……）。
- 依這個規則做一個選擇。
- 把問題縮小，對剩下的子問題重複。
- 不回頭改已經做的選擇。
它成立，需要兩件事同時為真：
- 貪心選擇性質：存在一個最佳解，它的第一步就是這個局部選擇。
- 最佳子結構：做完這一步，剩下的子問題的最佳解，接上去仍是原問題的最佳解。
只有第二個、沒有第一個，就是動態規劃的地盤：你必須試過每一種第一步。
2. 和動態規劃怎麼選
| 貪心 | 動態規劃 | |
|---|---|---|
| 第一步 | 只留一個候選 | 所有候選都算，再取最佳 |
| 時間 | 通常排序後線性或 (n\log n) | 狀態數 × 轉移 |
| 證明 | 要證明「存在最佳解採取這一步」 | 轉移本身在枚舉 |
| 寫錯的後果 | 程式很短，答案安靜地錯 | 較常是實作 bug |
實務順序：先找能證明的貪心。證明不動，再寫 DP。兩邊都太慢，才考慮近似（集合覆蓋那篇）或搜尋（NP 系列）。
3. 怎麼證明：交換論證
標準句型：
任取一個最佳解。若它的第一步不是貪心的選擇，就把那一步換成貪心的選擇。證明交換之後仍然可行，而且不會變差。於是存在一個以貪心選擇開頭的最佳解。接著對子問題歸納。
「我試了幾個例子都對」不是證明。第 7 節就是用來打破這種錯覺的。
4. 活動選擇
區間代表活動的 [開始, 結束)。同一時間只能進行一個，求最多能排幾個。
例：(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)。
規則：每次選結束時間最早、且不與已選活動重疊的那個。
先依結束時間排序：(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)。
- 選
(1,4)。 (3,5)與它重疊，跳過。(0,6)重疊，跳過。(5,7)在 4 之後開始，選它。(8,9)在 7 之後，選它。(5,9)與(5,7)重疊，跳過。
得到 3 個：(1,4), (5,7), (8,9)。這已是全部 6 個活動在單資源下的最大數量（時間軸上至少要三段不重疊，而這三段蓋滿了能蓋的範圍；也可暴力檢查沒有 4 個互不重疊）。
為什麼選「最早結束」而不是「最早開始」或「最短」？
交換論證：設最佳解的第一個活動是 (A)，貪心選的是結束最早的 (G)。(G) 的結束時間 (\le A) 的結束時間，所以 (G) 不會碰到 (A) 後面那些活動。把 (A) 換成 (G)，數量不變，仍然最佳。若改選最短活動，短活動可能卡在中間，兩側各浪費一段，反例見第 7 節。
加權版本（每個活動有權重，要總權重最大）沒有這個交換性質。那是區間 DP 或排序後的一維 DP，不要沿用本規則。
5. 分數背包與 0/1 背包
容量 5。三件物品：
| 物品 | 重量 | 價值 | 單位價值 |
|---|---|---|---|
| A | 2 | 6 | 3 |
| B | 3 | 6 | 2 |
| C | 2 | 2 | 1 |
分數背包可以切下一塊，只拿一部分重量，價值按比例。規則：依單位價值由高到低拿。
拿光 A（重 2、值 6），剩下容量 3，B 的重量剛好 3，拿光 B（值 6）。合計價值 12。C 不用拿。
0/1 背包不能切。這個例子兩種規則碰巧都是拿 A+B。把數字改成容量 5、物品 (2, 3), (3, 4), (4, 5)（重量、價值）：單位價值分別是 1.5、1.333、1.25。貪心會先拿第一件再拿第二件，價值 7，這次仍然最好。反例：容量 10，物品 (6, 7), (5, 5), (5, 5)。單位價值 7/6、1、1。貪心先拿第一件，剩下 4，兩件都放不進，價值 7。最佳是兩件重量 5 的，價值 10。
所以 0/1 背包走 DP（見背包教材與 DP 教材），分數背包才走貪心。證明仍是交換：最佳解若在單位價值較高的物品上留了空，而較低的物品拿了正的重量，把後者的一點重量換給前者，總價值上升，矛盾。
6. 霍夫曼編碼
目標：一組符號與出現次數，建成二元前綴碼，讓加權路徑長最短。前綴碼表示沒有任何碼是另一個碼的前綴，所以解碼時不用分隔符。
次數：W:4, X:6, Y:7, Z:15。
演算法：反覆取出頻率最小的兩棵樹，合併成父節點，父節點頻率是兩者之和，直到剩一棵。
- 取出 W(4)、X(6)，合併成 P(10)。
- 現在是 P(10)、Y(7)、Z(15)。取出 Y(7)、P(10)，合併成 Q(17)。
- 剩下 Q(17)、Z(15)，合併成根 R(32)。
左孩子編碼加 0，右孩子加 1。平手時較小的頻率放左邊。合併 Q(17) 與 Z(15) 時 Z 較小，所以 Z 在左：
R32
/ \
Z15 Q17
碼 0 / \
Y7 P10
碼 10 / \
W4 X6
110 111Z 的碼是 0，Y 是 10，W 是 110，X 是 111。左右對調不會改變下面的加權路徑長，只會改變碼字本身。
加權路徑長：(4\cdot 3 + 6\cdot 3 + 7\cdot 2 + 15\cdot 1 = 12+18+14+15 = 59)。
定長編碼每符號 2 位元，總長 ((4+6+7+15)\cdot 2 = 64)。霍夫曼更短。
正確性的直覺：頻率最低的兩個符號在某棵最佳樹裡可以是兄弟（它們的深度應該最深，否則和較高頻率的符號交換深度會更差）。合併它們等於把問題縮小一個符號。實作時用最小堆積每次取兩個最小頻率，時間 (O(n\log n))。
這和「資料壓縮」的關係：霍夫曼處理的是已知頻率的符號；它不利用符號之間的上下文。需要適應性或字典壓縮時，這只是第一層工具，不是全部。
7. 貪心會失敗的例子
活動選擇若改選「最短的活動」。 區間 (0,3), (2,4), (3,6)。最短的是 (2,4)，選了它之後左右都重疊，答案是 1。但 (0,3) 與 (3,6) 可以排兩個。所以「最短」不是正確的貪心規則；「最早結束」才是。
找零若面額是 {1, 3, 4}，要湊 6，而且每次都拿不大於餘額的最大面額。 先拿 4，剩下 2，再拿兩個 1，共 3 枚。最佳是兩個 3，共 2 枚。這是典型的「硬幣系統不是標準制」：貪心找零只在特定面額（例如 1、5、10、25）成立，一般面額要用 DP。
把這兩個反例記下來。以後每寫一個「看起來很順」的規則，先問：交換之後會不會變差？能不能做出一個小反例？
8. 圖上的三個貪心
細節在圖論教材，這裡只標出貪心選擇是什麼。
| 演算法 | 每一步的貪心選擇 | 為什麼能交換 |
|---|---|---|
| Dijkstra（非負權） | 取出目前距離估計最小的頂點，距離就此定案 | 非負權下，別的路徑不會比這個估計更短 |
| Prim | 把連到「樹外」的最便宜邊納入 | 切分定理：跨越切分的最輕邊屬於某棵 MST |
| Kruskal | 依權重由小到大，不構成環就納入 | 同一條切分定理，只是邊的考慮順序是全域排序 |
權重可以是負的時候，Dijkstra 的「定案」會錯，要改 Bellman-Ford。MST 的切分定理不要求權重為正，但通常假設權重可比較。負環是另一個問題，不屬於這三個演算法。
集合覆蓋的貪心（每次蓋掉最多尚未覆蓋的元素）沒有最佳選擇性質，只有近似比。那是近似演算法，不是本篇這種「得到最佳解」的貪心。見 10_SetCover_Teaching_Materials.tex。
9. 常見陷阱
- 排序鍵選錯還是能跑完。 活動選擇依開始時間排序，程式不會崩潰，答案會錯。先寫反例再寫程式。
- 加權活動沿用無權規則。 結束早但權重極低的活動會擠掉高權重活動。
- 分數背包的程式拿去解 0/1。 第 5 節的容量 10 反例直接打臉。
- 霍夫曼把頻率高的符號放深。 合併順序反了。每次都該取目前最小的兩個。
- Dijkstra 用在有負權的圖。 貪心定案不成立。
- 平手時不穩定。 結束時間相同的活動，先選哪個都還是最佳數量，但方案不唯一。題目若要求字典序最小的方案，平手規則要另外寫。
10. 練習題
- 活動
(0,2), (1,3), (2,5), (4,6), (5,8), (7,9)。用最早結束規則選出一組最大集合。 - 為上面這組活動舉一個「依開始時間最早」會選錯或選得較少的情況；若這個例子沒失敗，改一個區間讓它失敗。
- 分數背包容量 7，物品
(w,v) = (3,6), (4,6), (2,4)。最佳價值是多少？ - 符號
A:3, B:3, C:4, D:10。做出一棵霍夫曼樹，並計算加權路徑長。定長 2 位元的總長是多少？ - 為什麼 Kruskal 在「權重相同的多條邊」時，不同的平手處理仍得到最小生成樹，但樹的形狀可以不同？
參考答案
- 依結束時間已排序。選
(0,2)，下一個起點不早於 2 的是(2,5)，再下一個起點不早於 5 的是(5,8)。(7,9)與(5,8)重疊。共 3 個。(4,6)與(7,9)只能再湊出 2 個，較少。 - 把區間改成
(0,10), (1,2), (2,3)。依開始時間會先拿(0,10)，只剩 1 個；依結束時間會拿(1,2)再拿(2,3)，答案是 2。 - 單位價值分別是 2、1.5、2。先拿重量 3（價值 6）與重量 2（價值 4），容量剩 2，從重量 4 的物品切一半，價值再加 3。合計 13。整件拿重量 3 與 4 只有 12。
- 先合併 A、B 得 P(6)，再合併 P 與 C 得 Q(10)，再與 D(10) 合併。一種編碼：D 長度 1，C 長度 2，A 與 B 長度 3。加權路徑長 (10\cdot 1 + 4\cdot 2 + 3\cdot 3 + 3\cdot 3 = 10+8+9+9 = 36)。定長總長 ((3+3+4+10)\cdot 2 = 40)。
- 切分定理保證「某一條」最輕跨越邊可以加入，權重並列時每一條都是最輕，選哪條都存在一棵 MST 包含它。不同選擇得到的樹不同，總權重相同。
小結
貪心是「存在一個最佳解願意採取這個局部選擇」。證明用交換：換進去不會變差。活動選擇的正確規則是最早結束，分數背包的正確規則是單位價值，霍夫曼是反覆合併最小頻率。0/1 背包、一般面額找零、加權活動選擇都有小反例，那些要交給動態規劃。Dijkstra、Prim、Kruskal 是圖上已經證完的貪心，負權會打壞 Dijkstra 的定案。