第 11 章 中等 約 12 分鐘
貪婪演算法：每一步都選眼前最好的
找零錢用最大面額、寫作業挑分數最高的——貪婪法簡單暴力，但不一定最佳。
建議先看過： 10-dp
找零的本能
便利商店店員找你 36 元，他會怎麼給？
1 個 25 + 1 個 10 + 1 個 1？不對，應該是 1 個 25 + 1 個 10 + 1 個 1 = 36，總共 3 枚。
店員的腦袋是這樣跑的：
- 36 ≥ 25 嗎？給一枚 25，剩 11。
- 11 ≥ 10 嗎？給一枚 10，剩 1。
- 1 ≥ 1 嗎？給一枚 1，剩 0。完成。
每一步都「拿目前最大能用的」——這就是貪婪 (Greedy)。
貪婪的兩個關鍵字
- 每一步都做「當下看起來最好」的選擇。
- 不回頭、不反悔——選了就走，不重新評估。
經典例：活動選擇
你有 1 天，下列活動，最多參加幾場（不能重疊）？
| 活動 | 開始 | 結束 |
|---|---|---|
| A | 9:00 | 11:00 |
| B | 10:00 | 13:00 |
| C | 11:00 | 12:00 |
| D | 12:00 | 14:00 |
| E | 13:00 | 15:00 |
貪婪策略：永遠選「最早結束」的還沒衝突的活動。
按結束時間排：
- A 結束 11:00 → 選！
- C 結束 12:00、開始 11:00 ≥ 上一場結束 → 選！
- D 結束 14:00、開始 12:00 ≥ 12:00 → 選！
- E 開始 13:00 < 上一場結束 14:00 → 衝突，跳過
- B 跟前面衝突，跳過
答案：3 場（A, C, D）。
💡為什麼選「最早結束」？
直覺：越早結束，剩下的時間就越多，能塞越多場。 數學上可以證明這個策略是最佳的（但你不用記證明）。
貪婪 vs DP
兩個都解最佳化問題，差別：
| Greedy | DP | |
|---|---|---|
| 怎麼做 | 每步選當下最好 | 算過所有可能再挑最好 |
| 速度 | 通常 O(n log n) | 通常 O(n²) 或更高 |
| 保證 | 不一定最佳 ⚠️ | 保證最佳 |
| 何時用 | 有「貪婪選擇性質」時 | 大部分最佳化問題 |
貪婪會失敗的例子
找零題的反例：硬幣面額 {1, 4, 6}，要湊 8 元，最少幾枚？
貪婪：先拿 6，剩 2，拿 2 個 1 → 3 枚。 最佳：4 + 4 → 2 枚。
貪婪贏不了！ 因為「先拿最大」沒有考慮後續。
⚠️什麼時候能用貪婪？
有兩個條件：
- 貪婪選擇性質：每一步的最佳選擇，能延伸到整體最佳。
- 最佳子結構：剩下的問題仍是同一類型。
判斷困難 → 考試題目通常會給你提示。 看到「每步選最早結束 / 最便宜 / 最重」的字眼，多半就是貪婪。
📝考試會這樣考
題型一：活動選擇 / 區間排程。 給一堆活動的開始 / 結束時間，問最多選幾個不重疊。 怎麼做：按結束時間排，從早到晚選不衝突的。
題型二：找零題（硬幣面額固定）。 台灣硬幣 {1, 5, 10, 50} 是「canonical」面額，貪婪保證最佳。 但題目可能給特殊面額 {1, 4, 6}，這時貪婪會輸給 DP。
題型三：給情境問用 Greedy 還是 DP。 看「選擇之間有沒有相互影響」：
- 沒影響、每步獨立 → Greedy
- 後面的選擇會影響前面評估 → DP
這章記住
- 貪婪 = 每步選當下最好，不反悔。
- 不保證最佳，要看題目性質。
- 排序常常是貪婪的第一步（按結束時間、按重量、按 CP 值等）。
學習進度只存在你的瀏覽器，不會上傳。