[algorithms] Greedy Algorithms 貪心演算法

cover

視覺化概覽

flowchart TD
    A["排序候選項目\n依貪心策略排序"] --> B["取出下一個候選項目"]
    B --> C{"滿足約束條件？"}
    C -->|"是"| D["選擇：加入解集合"]
    C -->|"否"| E["跳過此項目"]
    D --> F["更新當前狀態"]
    E --> G{"還有候選項目？"}
    F --> G
    G -->|"是"| B
    G -->|"否"| H["回傳解集合\n局部最佳 → 全域最佳"]

什麼是貪心？

每一步都選擇當前最好的，不回頭。

找零 63 元，硬幣有 [1, 5, 10, 25]

貪心：
1. 選 25（剩 38）
2. 選 25（剩 13）
3. 選 10（剩 3）
4. 選 1（剩 2）
5. 選 1（剩 1）
6. 選 1（剩 0）

結果：25 + 25 + 10 + 1 + 1 + 1 = 6 枚

貪心 vs 動態規劃

比較	貪心	DP
策略	每步選最佳	考慮所有可能
回溯	不回頭	可能需要
速度	通常更快	可能較慢
正確性	不一定最佳	保證最佳

貪心適用條件

貪心選擇性質：局部最佳 → 全局最佳
最佳子結構：問題的最佳解包含子問題的最佳解

經典貪心問題

1. 活動選擇

問題：選擇最多不重疊的活動

貪心策略：每次選結束時間最早的活動

活動: [(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)]
      開始  結束

按結束時間排序: (1,2), (3,4), (5,7), (8,9)...

選擇: (1,2) → (3,4) → (5,7) → (8,9)
共 4 個活動

// 按結束時間排序
Arrays.sort(activities, (a, b) -> a.end - b.end);
 
List<Activity> selected = new ArrayList<>();
int lastEnd = 0;
 
for (Activity act : activities) {
    if (act.start >= lastEnd) {
        selected.add(act);
        lastEnd = act.end;
    }
}

2. 分數背包

問題：物品可以切割，背包容量有限，求最大價值

貪心策略：優先選價值密度（價值/重量）最高的

物品: [(10kg, $60), (20kg, $100), (30kg, $120)]
背包容量: 50kg

價值密度: 6, 5, 4（$/kg）

選擇順序:
1. 物品0 全部（10kg, $60）
2. 物品1 全部（20kg, $100）
3. 物品2 的 2/3（20kg, $80）

總價值: 60 + 100 + 80 = $240

3. 霍夫曼編碼

問題：建立最佳前綴編碼（壓縮）

貪心策略：每次合併頻率最小的兩個節點

字元頻率: a=45, b=13, c=12, d=16, e=9, f=5

建樹過程:
1. 合併 f(5) + e(9) = 14
2. 合併 c(12) + b(13) = 25
3. 合併 14 + d(16) = 30
4. 合併 25 + 30 = 55
5. 合併 a(45) + 55 = 100

編碼結果:
a: 0
b: 101
c: 100
d: 111
e: 1101
f: 1100

4. 硬幣找零（貪心版）

注意：貪心不一定得到最佳解！

硬幣 [1, 5, 10, 25]，金額 63
貪心: 25+25+10+1+1+1 = 6 枚 ✓ 正確

硬幣 [1, 3, 4]，金額 6
貪心: 4+1+1 = 3 枚
最佳: 3+3 = 2 枚 ✗ 貪心錯誤！

5. Kruskal 最小生成樹

問題：連接所有節點的最小權重邊集合

貪心策略：每次選權重最小且不形成環的邊

    1
   /|\
  4 | 3
 /  |  \
0---2---3
  3   4

選邊順序（按權重）:
1. 1-2 (權重 1)
2. 1-3 (權重 3) - 形成環，跳過
3. 0-2 (權重 3)
4. 2-3 (權重 4)

MST: 1-2, 0-2, 2-3，總權重 = 8

6. 工作排程

問題：每個工作有截止時間和利潤，一次只能做一個

貪心策略：優先安排利潤最高的工作

工作: [(截止=2, 利潤=100), (截止=1, 利潤=19),
       (截止=2, 利潤=27), (截止=1, 利潤=25)]

按利潤排序: 100, 27, 25, 19

安排:
時間 2: 工作0（利潤 100）
時間 1: 工作2（利潤 27）← 工作3 來不及了

總利潤: 127

貪心 vs DP 選擇指南

問題是否有貪心選擇性質？
├─ 是 → 用貪心（更快）
│   ├─ 活動選擇
│   ├─ 分數背包
│   ├─ 霍夫曼編碼
│   └─ MST (Kruskal/Prim)
└─ 否 → 用 DP（保證正確）
    ├─ 0/1 背包
    ├─ 硬幣找零（某些硬幣組合）
    └─ 最長共同子序列

時間複雜度

問題	時間複雜度
活動選擇	O(n log n)
分數背包	O(n log n)
霍夫曼編碼	O(n log n)
Kruskal MST	O(E log E)
工作排程	O(n² )

貪心演算法模板

// 1. 排序（根據貪心策略）
Arrays.sort(items, comparator);
 
// 2. 逐一處理
for (Item item : items) {
    if (canSelect(item)) {
        select(item);
        updateState();
    }
}
 
// 3. 回傳結果
return result;

Terry Yao's Blog

分類

目錄