貪婪演算法 (Greedy Algorithm) 是一種在每一步選擇中都採取在當前狀態下最好或最優 (即最有利) 的選擇，從而希望導致結果是全局最好或最優的演算法。這種方法每次做出選擇時，只考慮當前最優解，而不考慮未來的後果。

基本思想

貪婪演算法的核心思想是: 每一步都做出在當前狀態下看起來最好的選擇，而不考慮未來的後果。這種方法並不總是能得到最優解，但對於某些特定問題，貪婪策略可以保證得到全局最優解

基本步驟

1. 選擇: 根據某種標準，從當前可行的選擇中選出最優者
2. 可行性檢查: 判斷這個選擇是否導致問題無法繼續求解
3. 合併: 將這個選擇加入到已選擇的集合中
4. 重複: 重複上述步驟，直到達到結束條件

經典範例

• 找零問題 (Coin Change Problem): 給定不同面額的硬幣，要求用最少的硬幣數湊出指定金額。對於某些硬幣組合，貪婪法能得到最優解
• 活動選擇問題 (Activity Selection Problem): 選擇最多不重疊的活動，通常按照結束時間最早的活動優先選擇
• 最小生成樹 (Minimum Spanning Tree): 如 Kruskal 和 Prim 演算法，都是貪婪策略的應用
• 哈夫曼編碼 (Huffman Coding): 用於資料壓縮的哈夫曼樹構建過程

優點

• 實現簡單，通常只需一個迴圈或遞迴
• 執行效率高，時間複雜度低
• 適合於可以證明貪婪選擇性質和最優子結構的問題

缺點

• 並非所有問題都適用，對於某些問題可能無法得到最優解
• 需要證明問題具有「貪婪選擇性質」和「最優子結構」

舉例說明

活動選擇問題

假設有多個活動，每個活動有開始和結束時間，要求選擇最多不重疊的活動。貪婪策略是每次選擇結束時間最早且不與已選活動重疊的活動。

找零問題

如果硬幣是 [1, 3, 4]，我要湊 6 元，使用貪婪 (每次拿最大硬幣) 會得到哪個組合?

• 先拿最大但不超過 6 的 → 4 → 剩下 2
• 再拿最大 → 1 → 剩下 1
• 再拿最大 → 1 → 剩下 0

總共: 4 + 1 + 1 = 6，用了 3 枚硬幣

⚠️ 但是注意

最佳解其實是 3 + 3 = 6，只要 2 枚。
這就是貪婪演算法的陷阱 ——「局部最佳 ≠ 全域最佳」。

結論

貪婪演算法是一種簡單高效的演算法設計方法，適合於具有貪婪選擇性質和最優子結構的問題。在使用貪婪法時，需特別注意問題是否滿足這些性質，否則可能無法得到最優解。