用Python实战5个经典问题彻底掌握贪心算法贪心算法就像一位精明的商人总是在每个决策点选择当下看起来最有利的方案。这种活在当下的策略虽然简单却能高效解决许多实际问题。今天我们将通过五个经典案例从零开始拆解贪心算法的核心思想并用Python代码将其落地实现。1. 硬币找零问题从钱包到算法想象你在一家便利店做收银员需要给顾客找零63元。钱包里有50元、20元、10元、5元和1元的硬币如何用最少数量的硬币完成找零贪心算法的解决方案非常直观每次都选择不超过剩余金额的最大面额硬币。这种策略在日常生活中很常见但将其转化为算法需要明确几个关键点排序预处理将硬币按面额从大到小排序循环选取从最大面额开始尽可能多地使用当前面额金额更新每次选取后更新剩余找零金额def make_change(amount, coins): coins.sort(reverseTrue) # 降序排列 change [] for coin in coins: while amount coin: change.append(coin) amount - coin return change # 示例使用 coins [1, 5, 10, 20, 50] print(make_change(63, coins)) # 输出[50, 10, 1, 1, 1]这个算法的时间复杂度是O(n)其中n是硬币种类数。虽然对于标准货币体系它能得到最优解但在某些特殊情况下如硬币面额为[1, 3, 4]找零6元贪心算法会得到次优解411而非33。2. 会议室安排问题最大化资源利用率假设你是一家公司的行政主管需要安排尽可能多的会议使用同一间会议室。每个会议有固定的开始和结束时间如何安排才能最大化会议室的使用效率这个问题被称为活动选择问题其贪心策略是优先选择结束时间最早的活动。这样能为后续活动留下更多时间。实现这一算法需要按结束时间排序所有活动选择第一个活动作为起点依次选择不与已选活动时间冲突的后续活动def schedule_meetings(meetings): # 按结束时间排序 meetings.sort(keylambda x: x[1]) selected [meetings[0]] last_end meetings[0][1] for start, end in meetings[1:]: if start last_end: selected.append((start, end)) last_end end return selected # 示例数据(开始时间, 结束时间) meetings [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)] print(schedule_meetings(meetings)) # 输出[(1,4), (5,7), (8,11)]这个算法的时间复杂度主要来自排序步骤为O(n log n)。它完美展示了贪心算法的核心思想通过局部最优选择最早结束的活动来达到全局最优最多活动安排。3. 霍夫曼编码数据压缩的艺术在数据存储和传输中如何用最少的比特表示信息霍夫曼编码利用字符出现频率构建最优前缀码高频字符用短码低频字符用长码。实现霍夫曼编码的关键步骤统计字符频率构建霍夫曼树优先队列生成编码表递归遍历树编码原始文本import heapq from collections import defaultdict class Node: def __init__(self, char, freq): self.char char self.freq freq self.left None self.right None def __lt__(self, other): return self.freq other.freq def build_huffman_tree(text): freq defaultdict(int) for char in text: freq[char] 1 heap [Node(char, f) for char, f in freq.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) merged Node(None, left.freq right.freq) merged.left left merged.right right heapq.heappush(heap, merged) return heap[0] def generate_codes(root, current_code, codes): if root is None: return if root.char is not None: codes[root.char] current_code generate_codes(root.left, current_code 0, codes) generate_codes(root.right, current_code 1, codes) # 示例使用 text abracadabra root build_huffman_tree(text) codes {} generate_codes(root, , codes) print(霍夫曼编码表:, codes)霍夫曼编码的贪心之处在于每次都合并频率最低的两个节点这种局部最优选择最终导致全局最优的压缩效果。该算法的时间复杂度为O(n log n)广泛应用于ZIP、JPEG等压缩格式中。4. 最小生成树连接世界的最优方式在建设通信网络时如何用最少的电缆连接所有城市这就是最小生成树(MST)问题。Prim算法采用贪心策略逐步构建MST从任意节点开始每次选择连接树与非树节点的最小权重边将新节点加入树中重复直到包含所有节点import heapq def prim_mst(graph): n len(graph) mst [] visited [False] * n heap [(0, 0, -1)] # (weight, node, parent) while heap: weight, u, parent heapq.heappop(heap) if visited[u]: continue visited[u] True if parent ! -1: mst.append((parent, u, weight)) for v, w in graph[u]: if not visited[v]: heapq.heappush(heap, (w, v, u)) return mst # 示例图邻接表表示 graph [ [(1, 2), (2, 3)], # 节点0 [(0, 2), (2, 1), (3, 1)], # 节点1 [(0, 3), (1, 1), (3, 4)], # 节点2 [(1, 1), (2, 4)] # 节点3 ] print(prim_mst(graph)) # 输出[(0, 1, 2), (1, 3, 1), (1, 2, 1)]Prim算法使用最小堆来高效选择最小权重边时间复杂度为O(E log V)。这种贪心策略确保每次局部最优选择最终形成全局最优的最小生成树。5. 快递路线规划最近邻启发式快递员每天需要拜访多个地点后返回仓库如何规划路线使总距离最短这是著名的旅行商问题(TSP)的变种。虽然TSP没有多项式时间的精确解但贪心算法可以提供不错的近似解。最近邻启发式算法步骤从仓库出发每次前往最近的未访问客户点重复直到所有客户被访问返回仓库import math def nearest_neighbor(warehouse, customers): unvisited customers.copy() route [warehouse] current warehouse while unvisited: nearest min(unvisited, keylambda x: distance(current, x)) route.append(nearest) unvisited.remove(nearest) current nearest route.append(warehouse) # 返回仓库 return route def distance(p1, p2): return math.sqrt((p1[0]-p2[0])**2 (p1[1]-p2[1])**2) # 示例使用 warehouse (0, 0) customers [(2, 3), (5, 1), (4, 2), (6, 4)] print(nearest_neighbor(warehouse, customers))虽然这种贪心策略不能保证全局最优但在实际应用中通常能得到较好的解决方案特别是当客户点分布相对均匀时。算法时间复杂度为O(n²)适合中小规模问题。