貪心算法入門：核心思想、最優子結構、與動態規劃的區別

貪心算法是解決最優化問題的經典策略：每步做局部最優選擇，期望得到全局最優解。本文通過找零錢、活動安排問題，講解貪心選擇性質、最優子結構、與動態規劃的本質區別。

1. 核心概念：局部最優 → 全局最優？

貪心算法：每步在當前狀態下做看起來最好的選擇，不回溯、不考慮子問題最優解。

動態規劃：基於子問題最優解構建全局最優，通常自底向上、有重疊子問題。

2. 經典案例：找零錢問題

硬幣面值：0.25、0.10、0.05、0.01 元。找零 0.63 元。

貪心策略：每次取不超過剩餘金額的最大面值。

0.63 → 0.25 (剩 0.38)
0.38 → 0.25 (剩 0.13)
0.13 → 0.10 (剩 0.03)
0.03 → 0.01 × 3
共 6 枚硬幣（最優）

✅ 此面值體系下貪心得最優解。

反例：面值 0.11、0.10、0.01。找零 0.15。

貪心：0.11 + 0.01×4 = 5 枚
最優：0.10 + 0.05 (若無 0.05 則 0.10+0.01×5=6枚)
實際最優：0.10 + 0.01×5 = 6 枚？等等...
更好反例：面值 1、3、4。找零 6。
貪心：4+1+1 = 3 枚
最優：3+3 = 2 枚 ❌ 貪心失效

3. 活動安排問題：貪心正確性證明

n 個活動 (s_i, f_i)，選最大相容子集。貪心策略：按結束時間升序，每次選最早結束的相容活動。

證明框架（數學歸納法）：

1. 存在最優解包含貪心選擇（活動 1）
2. 選擇後，子問題結構相同（剩餘相容活動）
3. 歸納假設：貪心對子問題最優 → 全局最優

4. 貪心算法兩大核心性質

5. 貪心 vs 動態規劃：0-1 背包 vs 分數背包

• 分數背包：可取物品部分 → 貪心（按單位價值排序）最優
• 0-1 背包：只能整取/不取 → 貪心失效，需 DP

本質區別：貪心決策不可逆、無後效性；DP 決策基於子問題最優、有後效性。

6. 適用場景與局限

• ✅ 最小生成樹、單源最短路徑、霍夫曼編碼、活動安排、分數背包
• ❌ 0-1 背包、最長公共子序列、編輯距離（需 DP）
• 🔶 近似算法：某些 NP-Hard 問題貪心給出可接受近似解

總結

貪心算法簡單高效，但非萬能。判斷是否適用需嚴格證明貪心選擇性質。工程上：先嘗試貪心，失效再上 DP/回溯/啟發式。理解「局部最優 → 全局最優」的邊界，是算法設計的核心功力。

1. 上一篇文章： C++ STL next_permutation 算法詳解：生成全排列的字典序遞增原理
2. 下一篇文章： C 指針賦值陷阱：未初始化指針導致段錯誤的真相

關於C語言

sizeof 深度解析：關鍵字、運算符與「非函數」的三重身份

sizeof 的三重身份真相 在 C 語言中，sizeof

C 語言 volatile 關鍵字深度解析：編譯器優化抑制、硬體暫存器、中斷服務、多執行緒共享變數

核心語義：告訴編譯器「此變數隨時可能被外部不可見方式改變」

C# 2005 使用 SqlCommand 執行 T-SQL 查詢員工人數

若要使用資料命令將 Transact-SQL 陳述式傳送至

C 語言動態記憶體管理深度解析：malloc/free/realloc 實戰與鏈表應用

核心函式原型 #include <stdlib.h&g