别再死记硬背了！用Python搞定贪心算法，从找零钱到路线规划一次讲透

用Python玩转贪心算法从零钱兑换到智能路径规划的实战指南贪心算法就像一位精明的商人永远选择当下最有利可图的交易。这种活在当下的算法思维在解决许多实际问题时展现出惊人的效率。本文将带你用Python实现五个经典场景的贪心算法应用每个案例都配有可直接运行的代码和详细解析。1. 零钱兑换从超市收银台到自动售货机零钱兑换问题是理解贪心算法最直观的入口。想象你正在开发一个自动售货机的找零系统如何用最少数量的硬币完成找零贪心策略的核心每次选择不超过剩余金额的最大面额硬币。这种策略在大多数货币体系下都能得到最优解。def make_change(amount, coins): coins.sort(reverseTrue) # 降序排列面值 change [] for coin in coins: while amount coin: change.append(coin) amount - coin return change if amount 0 else None # 无法正好找零的情况 # 人民币面值示例 coins [100, 50, 20, 10, 5, 1] print(make_change(176, coins)) # 输出: [100, 50, 20, 5, 1]注意贪心算法并不总是能得到最优解。如果硬币面值为[25, 10, 1]要兑换30分贪心法会给出[25, 1, 1, 1, 1, 1]而非更优的[10, 10, 10]实际应用中的优化技巧预处理硬币面值确保降序排列添加无法找零的边界条件处理考虑货币系统的特殊性如美国硬币体系2. 活动安排会议室预订系统的智能算法假设你正在开发一个公司会议室预订系统如何安排最多数量的会议这就是经典的活动选择问题。关键洞察优先选择结束时间早的活动能为后续安排留出更多时间。def schedule_activities(activities): # 按结束时间排序 sorted_acts sorted(activities, keylambda x: x[1]) selected [sorted_acts[0]] for act in sorted_acts[1:]: if act[0] selected[-1][1]: # 检查时间是否冲突 selected.append(act) return selected # 每个活动格式(开始时间, 结束时间) meetings [(1,3), (2,5), (3,6), (5,7), (8,9)] print(schedule_activities(meetings)) # 输出: [(1,3), (3,6), (8,9)]性能对比表方法时间复杂度空间复杂度是否最优贪心算法O(n log n)O(n)是暴力枚举O(2^n)O(n)是动态规划O(n^2)O(n^2)是3. 数据压缩手把手实现霍夫曼编码霍夫曼编码是ZIP、JPEG等压缩技术的核心算法之一。让我们从零实现这个优雅的贪心算法。构建霍夫曼树的步骤统计字符频率将每个字符作为独立节点重复合并频率最低的两个节点直到只剩一个根节点import heapq from collections import defaultdict class HuffmanNode: def __init__(self, charNone, freq0): 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 [HuffmanNode(char, f) for char, f in freq.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) merged HuffmanNode(freqleft.freq right.freq) merged.left left merged.right right heapq.heappush(heap, merged) return heap[0] # 生成编码表示 def generate_codes(node, prefix, codebook{}): if node is not None: if node.char is not None: codebook[node.char] prefix generate_codes(node.left, prefix 0, codebook) generate_codes(node.right, prefix 1, codebook) return codebook # 示例 text this is an example for huffman encoding tree build_huffman_tree(text) codes generate_codes(tree) print(Huffman Codes:, codes)4. 网络布线最小生成树的两种实现在建设计算机网络或电力网络时如何用最少的线缆连接所有节点最小生成树提供了完美解决方案。Prim算法实现import heapq def prim_mst(graph): mst [] visited set() start_node next(iter(graph)) visited.add(start_node) edges [ (cost, start_node, to) for to, cost in graph[start_node].items() ] heapq.heapify(edges) while edges: cost, frm, to heapq.heappop(edges) if to not in visited: visited.add(to) mst.append((frm, to, cost)) for to_next, cost in graph[to].items(): if to_next not in visited: heapq.heappush(edges, (cost, to, to_next)) return mst # 图表示为邻接表 graph { A: {B: 2, D: 1}, B: {A: 2, D: 3, C: 1}, C: {B: 1, D: 5}, D: {A: 1, B: 3, C: 5} } print(Prims MST:, prim_mst(graph))Kruskal算法实现class DisjointSet: def __init__(self, vertices): self.parent {v: v for v in vertices} def find(self, item): while self.parent[item] ! item: item self.parent[item] return item def union(self, set1, set2): self.parent[set1] set2 def kruskal_mst(graph): mst [] vertices list(graph.keys()) ds DisjointSet(vertices) edges [] for u in graph: for v, w in graph[u].items(): edges.append((w, u, v)) edges.sort() for edge in edges: w, u, v edge root_u ds.find(u) root_v ds.find(v) if root_u ! root_v: mst.append((u, v, w)) ds.union(root_u, root_v) return mst print(Kruskals MST:, kruskal_mst(graph))5. 物流优化智能路径规划实战物流公司每天面临的核心问题如何规划送货路线才能行驶最短距离贪心算法提供了一个实用的近似解。import math def calculate_distance(p1, p2): return math.sqrt((p1[0]-p2[0])**2 (p1[1]-p2[1])**2) def greedy_tsp(locations): unvisited locations[1:] # 起点固定 current locations[0] route [current] total_distance 0 while unvisited: nearest min(unvisited, keylambda x: calculate_distance(current, x)) total_distance calculate_distance(current, nearest) route.append(nearest) unvisited.remove(nearest) current nearest # 返回起点 total_distance calculate_distance(current, locations[0]) route.append(locations[0]) return route, total_distance # 仓库和客户位置 (x,y坐标) warehouse (0, 0) customers [(2,4), (3,1), (5,2), (4,3)] route, distance greedy_tsp([warehouse] customers) print(f配送路线: {route}) print(f总距离: {distance:.2f})路径优化技巧结合k-means先对客户聚类分区配送考虑实时交通数据动态调整混合使用2-opt等局部优化算法提升解质量