Python實現貪心算法(Greedy Algorithm)

概念

貪心算法是一種在每一步選擇中都采取當前狀態下最優的選擇，從而希望導致結果是全局最優的算法策略。

基本特點

1. 局部最優選擇：每一步都做出當前看起來最佳的選擇
2. 不可回退：一旦做出選擇，就不可更改
3. 高效性：通常比其他全局優化算法更快
4. 不保證全局最優：但能得到近似最優解

基本實現框架

（以分數背包問題為栗子）

def greedy_algorithm(items, capacity):# 通常先按某種規則排序items.sort(key=lambda x: x[1]/x[0], reverse=True)#按單位重量價值（value/weight）降序排序total_value = 0 #背包中物品的總價值selected_items = [] #選擇的物品列表（完整或部分物品）#開始選擇for item in items:if capacity >= item[0]:capacity -= item[0]total_value += item[1]selected_items.append(item)else:# 可選: 部分物品的情況(如分數背包問題)fraction = capacity / item[0]total_value += item[1] * fractionselected_items.append((item[0]*fraction, item[1]*fraction))breakreturn total_value, selected_items

經典應用示例 😍 😍

1. 找零錢問題

def coin_change(coins, amount):coins.sort(reverse=True)count = 0change = []for coin in coins:while amount >= coin:amount -= coincount += 1change.append(coin)return count if amount == 0 else -1, change# 示例
coins = [25, 10, 5, 1]
print(coin_change(coins, 63))  # 輸出: (6, [25, 25, 10, 1, 1, 1])

2. 區間調度問題

def interval_scheduling(intervals):# 按結束時間排序intervals.sort(key=lambda x: x[1])selected = []last_end = -float('inf')for start, end in intervals:if start >= last_end:selected.append((start, end))last_end = endreturn selected# 示例
intervals = [(1, 3), (2, 4), (3, 5), (4, 6)]
print(interval_scheduling(intervals))  # 輸出: [(1, 3), (3, 5)]

3. 霍夫曼編碼(數據壓縮)

import heapqdef huffman_encoding(freq):heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]heapq.heapify(heap)while len(heap) > 1:lo = heapq.heappop(heap)hi = heapq.heappop(heap)for pair in lo[1:]:pair[1] = '0' + pair[1]for pair in hi[1:]:pair[1] = '1' + pair[1]heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))# 示例
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
print(huffman_encoding(freq))

適用場景

1. 問題具有貪心選擇性質：局部最優能導致全局最優
2. 最優子結構：問題的最優解包含子問題的最優解
3. 典型應用：
   • 最小生成樹(Prim和Kruskal算法)
   • 最短路徑問題(Dijkstra算法)
   • 背包問題的分數版本
   • 任務調度問題
   • 文件壓縮(霍夫曼編碼)

貪心算法的局限性👀👀

1. 不總是能得到全局最優解
2. 需要證明問題的貪心選擇性質
3. 對某些問題可能需要結合其他算法(如動態規劃)

貪心 vs 動態規劃💪💪

特性	貪心算法	動態規劃
決策	每個階段做局部最優選擇	考慮所有可能的子問題
復雜度	通常更低	通常更高
最優解保證	不總是	總是
存儲需求	通常更少	需要存儲子問題結果
典型問題	找零錢、任務調度	背包問題、最長子序列

總結

貪心算法因其高效性在實際工程中應用廣泛，但使用時需要仔細分析問題是否適合貪心策略。😼😼