Learning Objectives
- 說明貪婪演算法「每一步選當下最好的、選了就不回頭」的做法
- 用依結束時間排序的貪婪法解活動選擇問題，並舉出其他排序方式的反例
- 追蹤找零的貪婪法，說明面額 1、5、10、50 可以、面額 1、3、4 不行
- 分辨分數背包（貪婪可解）與 0/1 背包（貪婪不可解）
- 用貪婪選擇性質與最佳子結構，直覺判斷貪婪法什麼時候行得通
每一步都選眼前最好的
校慶當天有很多場活動，時間互相重疊。你想參加的場次越多越好，但同一時間只能在一個地方。該怎麼挑？
一種很自然的想法是：每一步都做當下看起來最好的選擇，選了就不再回頭修改。這種策略叫做貪婪演算法（greedy algorithm）。 上一課的 Kruskal 每次挑最便宜的邊、Prim 每次加入最便宜的節點，都是貪婪法。
貪婪法通常寫起來很短、跑得很快（常常只是一次排序加一次掃描），問題是不一定正確： 眼前最好的選擇，有時會讓後面的選擇變差。這一課用三個問題看貪婪法什麼時候行得通、什麼時候會失敗：
| 問題 | 貪婪的選法 | 結果 |
|---|---|---|
| 活動選擇 | 先選最早結束的活動 | 一定最多 |
| 找零 | 先用面額最大的硬幣 | 看面額：台灣硬幣可以，有些面額不行 |
| 背包 | 先拿每公斤價值最高的 | 可以切開拿（分數背包）可以；整件拿（0/1 背包）不行 |
活動選擇：先選最早結束的
每個活動有開始與結束時間 [開始, 結束]；兩個活動不重疊的條件是：後一個的開始時間 ≥ 前一個的結束時間。目標是選出最多個互不重疊的活動。
「當下最好」可以有好幾種解讀，先看看哪些會出錯：
| 策略 | 反例 | 貪婪選到 | 最佳 |
|---|---|---|---|
| 先選最早開始的 | [0, 10]、[1, 2]、[3, 4] | 1 個（[0, 10] 擋住其他） | 2 個 |
| 先選最短的 | [1, 5]、[4, 7]、[6, 10] | 1 個（最短的 [4, 7] 和兩邊都重疊） | 2 個 |
| 先選最早結束的 | 找不到反例 |
先選最早結束的活動，理由是：它讓你最早空出來，剩下的時間最多。更精確地說，假設某個最佳解的第一個活動不是最早結束的那個， 把它換成最早結束的活動，仍然不會和後面的活動重疊，個數也一樣，所以「先選最早結束的」至少和最佳解一樣好。 選了它之後，剩下的問題是「在它結束之後的活動裡，再選最多個」，和原來的問題同一種形式。
做法：把活動依結束時間排序，記住已選活動的最晚結束時間 last_end，依序看每個活動，開始時間 ≥ last_end 就選。
排序 O(n log n)，掃描 O(n)。
活動選擇：排序後掃一遍
排序後，▲ 由左往右看每個活動。只要它的開始時間不早於 last_end，就選它，並把 last_end 改成它的結束時間。8 個活動選出 4 個：[1, 4]、[5, 7]、[8, 11]、[12, 14]。
想一想：活動選擇
下面的程式會印出什麼？
acts = [[1, 3], [2, 5], [4, 7], [6, 9], [8, 10]]
acts.sort(key=lambda x: x[1])
count, last_end = 0, 0
for s, e in acts:
if s >= last_end:
count += 1
last_end = e
print(count)
有人改成「先選持續時間最短的活動」。下面哪一組活動能說明這個策略不一定最好？
貪婪法什麼時候行得通
活動選擇的正確性靠的是兩件事，這也是判斷貪婪法能不能用的直覺：
- 貪婪選擇性質：一定存在一個最佳解，包含貪婪法第一步選的東西。（活動選擇：可以把最佳解的第一個活動換成最早結束的那個）
- 最佳子結構：做完第一步之後，剩下的部分是一個同類型、規模更小的問題，而且它的最佳解加上第一步，就是整體的最佳解。
缺了第 1 點，貪婪法第一步就可能走錯，而且不會回頭。要證明貪婪法正確，通常就是證明這種「換掉也不會變差」的性質； 要說明貪婪法不對，只要找到一個反例就夠了。
下面的找零問題，就是同一個貪婪法換了一組面額就失敗的例子。
找零：先用最大的面額
收銀機要找 87 元，想用最少枚硬幣。直覺的做法是：先用最大的 50 元，能用幾枚就用幾枚，剩下的再用 10 元，依此類推。
用台灣的硬幣面額 1、5、10、50（不考慮 20 元硬幣），這個方法一定得到最少的枚數。但換一組面額就不一定了： 面額 1、3、4，要湊 6 元，貪婪法先拿 4 元，剩下 2 元只能用兩個 1 元，共 3 枚； 可是 3 + 3 只要 2 枚。先拿最大的 4，反而讓剩下的 2 元變得難湊。
下面的範例把兩組面額都跑一次。
找零的貪婪法：成功與失敗
▲ 指著目前的面額。湊 87 元用了 7 枚，這是最少的。湊 6 元時，貪婪法用 4 + 1 + 1 共 3 枚，但 3 + 3 只要 2 枚：貪婪法在這組面額上失敗了。第 21 課會用動態規劃算出真正最少的枚數。
分數背包：可以切開拿
背包最多裝 50 公斤，有三樣東西：
| 東西 | 重量 | 價值 | 每公斤價值 |
|---|---|---|---|
| 甲 | 10 公斤 | 60 | 6 |
| 乙 | 20 公斤 | 100 | 5 |
| 丙 | 30 公斤 | 120 | 4 |
如果東西可以切開，只拿一部分（像散裝的米、咖啡豆），這叫分數背包（fractional knapsack）。 貪婪法是：依每公斤價值由高到低，能整個拿就整個拿，最後一樣裝不下就切一部分把背包填滿。這樣一定是最大價值， 因為每一公斤的空間都放了當時能放的最有價值的東西。
如果東西只能整件拿或不拿，就變成 0/1 背包，同樣的貪婪法會失敗：先拿甲、乙（30 公斤，價值 160）， 丙放不下，總價值 160；但拿乙、丙（50 公斤）價值是 220。0/1 背包要用第 22 課的動態規劃解。
範例的每公斤價值剛好都是整數，所以全程用整數計算，三種語言的輸出才會一致。
分數背包：每公斤價值高的先拿
排序後依序是每公斤 6、5、4 的東西。前兩樣整個拿，背包剩 20 公斤；第三樣 30 公斤裝不下，只拿 20 公斤，價值 4 × 20 = 80。總價值 240。
想一想：找零與背包
用範例的 greedy_change，面額 [50, 10, 5, 1] 湊 68 元，共用幾枚？
面額 1、3、4 湊 6 元，貪婪法得到 3 枚，最少其實是 2 枚。從這個例子可以得到什麼結論？
為什麼「依每公斤價值由高到低拿」適用於分數背包，卻不適用於 0/1 背包？
實作：最少要射幾支箭
牆上有幾顆橫向的長條氣球，每顆用 [左端, 右端] 表示。在位置 x 射一支垂直的箭，會射破所有「左端 ≤ x ≤ 右端」的氣球。最少要射幾支箭才能射破全部？
貪婪法和活動選擇很像：依右端排序，箭射在第一顆氣球的右端，凡是左端不超過這個位置的氣球都會被射破；遇到射不到的氣球，就在它的右端再射一支。
重點整理
- 貪婪演算法每一步選當下最好的，選了就不回頭；通常是排序加一次掃描，又短又快
- 正確的前提是貪婪選擇性質（某個最佳解包含貪婪的第一步）和最佳子結構（剩下的是同類型的小問題）
- 活動選擇：依結束時間排序，能選就選，一定最多；「最早開始」「最短」都有反例
- 找零：台灣硬幣面額可以用貪婪法；面額 1、3、4 湊 6 元，貪婪法 3 枚、最佳 2 枚
- 分數背包可以用貪婪法；0/1 背包不行
- 要說明貪婪法不對，找一個反例就夠了
下一課：動態規劃入門。貪婪法只看眼前的一步，動態規劃則把所有子問題的答案記下來再組合，可以解出面額 1、3、4 的找零問題。