基本思想
貪婪演算法在每個決策點都選擇當下最有利的選項，不考慮未來影響。
- 選擇函數：選擇下一個最優元素
- 可行性檢查：確保選擇滿足約束條件
- 目標函數：更新當前最佳解
找錢問題
def greedy_change(money, coins=[100, 50, 10, 5, 1]):
result = []
for coin in sorted(coins, reverse=True):
while money >= coin:
money -= coin
result.append(coin)
return result
活動選擇問題
選擇最多不相衝突的活動，按結束時間排序後貪婪選擇。
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
貪婪 vs 動態規劃
貪婪演算法不一定能得到全域最優解（如 0/1 背包問題），但在特定問題下（如找錢問題、活動選擇、最小生成樹）可以得到最優解。關鍵在於問題是否具有貪婪選擇性質：局部最優選擇能導致全域最優解。