贪心算法全攻略

一、贪心算法概述1.1 什么是贪心算法定义贪心算法Greedy Algorithm是指在每一步选择中都采取当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的算法。核心思想局部最优 → 全局最优1.2 生活类比场景贪心选择结果找零钱每次都拿最大面额硬币数量最少 ✅吃自助餐先拿最贵的海鲜不一定吃得最多 ❌爬山每次都往最陡的方向走可能到的是局部山顶 ❌1.3 贪心算法的基本步骤text第1步建立数学模型来描述问题 第2步把求解的问题分成若干个子问题 第3步对每个子问题求解得到子问题的局部最优解 第4步把子问题的局部最优解合成原问题的一个解二、贪心算法的适用条件2.1 两个核心性质性质说明示例贪心选择性质全局最优解可以通过局部最优选择得到找零钱问题最优子结构性质问题的最优解包含子问题的最优解最短路径问题2.2 贪心 vs 动态规划对比维度贪心算法动态规划决策方式单次决策不回头多阶段决策考虑所有可能依赖关系只依赖当前状态依赖之前所有状态适用条件贪心选择最优子结构最优子结构重叠子问题时间复杂度通常较低O(n)或O(nlogn)通常较高O(n²)或更高空间复杂度通常较低O(1)或O(n)通常较高需要存储中间结果三、经典贪心问题与代码实现3.1 找零钱问题Coin Change问题描述有面额 [1, 5, 10, 25] 的硬币用最少的硬币凑出指定金额。pythondef coin_change(coins, amount): 贪心解法每次使用最大面额的硬币 参数: coins: 硬币面额列表需降序排列 amount: 需要凑的金额 返回: 最少硬币数量无法凑出则返回 -1 # 先将硬币按面额从大到小排序 coins.sort(reverseTrue) count 0 # 硬币总数 result [] # 记录每枚硬币面额 for coin in coins: # 当前硬币最多能用多少个 num amount // coin if num 0: count num amount - num * coin result.extend([coin] * num) if amount 0: break # 如果最终金额不为0说明无法凑出 if amount ! 0: return -1 print(f使用的硬币: {result}) return count # 测试代码 if __name__ __main__: coins [25, 10, 5, 1] amount 63 result coin_change(coins, amount) print(f凑够 {amount} 元需要 {result} 枚硬币) # 输出: # 使用的硬币: [25, 25, 10, 1, 1, 1] # 凑够 63 元需要 6 枚硬币⚠️ 注意贪心算法并非在所有币种下都有效python# 反例coins [1, 3, 4], amount 6 # 贪心411 3枚 ❌ # 最优33 2枚 ✅3.2 活动选择问题Activity Selection问题描述有n个活动每个活动有开始和结束时间选择尽可能多的互不冲突的活动。pythondef activity_selection(activities): 贪心解法每次选择结束时间最早的活动 参数: activities: 列表每个元素为 (开始时间, 结束时间) 返回: 选中的活动列表 # 按结束时间排序贪心选择结束越早留给后面的时间越多 activities.sort(keylambda x: x[1]) selected [] last_end_time 0 for start, end in activities: # 如果当前活动开始时间 上一个选中活动的结束时间 if start last_end_time: selected.append((start, end)) last_end_time end return selected # 测试代码 if __name__ __main__: # 活动列表(开始时间, 结束时间) activities [ (1, 4), # 活动A (3, 5), # 活动B (0, 6), # 活动C (5, 7), # 活动D (3, 8), # 活动E (5, 9), # 活动F (6, 10), # 活动G (8, 11), # 活动H (8, 12), # 活动I (2, 13), # 活动J (12, 14) # 活动K ] selected activity_selection(activities) print(f最多可以选择 {len(selected)} 个活动:) for start, end in selected: print(f {chr(65 selected.index((start, end)))}: {start} - {end})时间复杂度O(n log n)主要是排序3.3 哈夫曼编码Huffman Coding问题描述根据字符出现频率构造最优二叉树实现数据压缩。pythonimport heapq from collections import Counter class HuffmanNode: 哈夫曼树节点 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): 构建哈夫曼树 参数: text: 输入文本 返回: 哈夫曼树的根节点 # 1. 统计字符频率 freq_map Counter(text) # 2. 构建最小堆 heap [] for char, freq in freq_map.items(): heapq.heappush(heap, HuffmanNode(char, freq)) # 3. 重复合并频率最小的两个节点 while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) # 创建父节点字符为None频率为两子节点之和 parent HuffmanNode(None, left.freq right.freq) parent.left left parent.right right heapq.heappush(heap, parent) return heap[0] if heap else None def generate_huffman_codes(node, code, codes{}): 生成哈夫曼编码表递归 参数: node: 当前节点 code: 当前编码 codes: 编码字典 if node is None: return # 叶子节点有字符 if node.char is not None: codes[node.char] code return # 左子树编码加 0右子树加 1 generate_huffman_codes(node.left, code 0, codes) generate_huffman_codes(node.right, code 1, codes) def huffman_encode(text): 哈夫曼编码完整流程 # 构建哈夫曼树 root build_huffman_tree(text) # 生成编码表 codes {} generate_huffman_codes(root, , codes) # 编码文本 encoded_text .join(codes[char] for char in text) return codes, encoded_text, root def huffman_decode(encoded_text, root): 哈夫曼解码 decoded_text current root for bit in encoded_text: if bit 0: current current.left else: current current.right # 到达叶子节点 if current.char is not None: decoded_text current.char current root return decoded_text # 测试代码 if __name__ __main__: text AABBBCCCCDDDDD print(f原始文本: {text}) print(f原始长度: {len(text) * 8} 位 (ASCII编码)) codes, encoded, root huffman_encode(text) print(f\n哈夫曼编码表:) for char, code in sorted(codes.items()): print(f {char}: {code}) print(f\n编码结果: {encoded}) print(f编码长度: {len(encoded)} 位) print(f压缩率: {len(encoded) / (len(text) * 8) * 100:.2f}%) decoded huffman_decode(encoded, root) print(f\n解码验证: {decoded})3.4 分数背包问题Fractional Knapsack问题描述物品可分割在背包容量限制下使总价值最大。pythondef fractional_knapsack(items, capacity): 分数背包问题贪心解法 贪心策略按单位重量价值价值/重量从高到低选择 参数: items: 列表每个元素为 (重量, 价值) capacity: 背包容量 返回: 总价值和所选物品信息 # 计算单位重量价值并排序 items_with_ratio [] for weight, value in items: ratio value / weight items_with_ratio.append((weight, value, ratio)) # 按单位价值降序排列 items_with_ratio.sort(keylambda x: x[2], reverseTrue) total_value 0.0 remaining_capacity capacity selected [] for weight, value, ratio in items_with_ratio: if remaining_capacity 0: break if weight remaining_capacity: # 可以装下整个物品 total_value value remaining_capacity - weight selected.append((weight, value, 1.0)) # 1.0表示全拿 else: # 只能装一部分 fraction remaining_capacity / weight total_value value * fraction selected.append((weight, value, fraction)) remaining_capacity 0 return total_value, selected # 测试代码 if __name__ __main__: items [ (10, 60), # 物品1: 重量10, 价值60 (20, 100), # 物品2: 重量20, 价值100 (30, 120) # 物品3: 重量30, 价值120 ] capacity 50 total_value, selected fractional_knapsack(items, capacity) print(f背包容量: {capacity}) print(f总价值: {total_value}) print(f\n选择的物品:) for i, (weight, value, fraction) in enumerate(selected): print(f 物品{i1}: 拿取 {fraction*100:.1f}% (重量 {weight*fraction:.1f}))3.5 最小生成树 - Prim算法问题描述给定无向连通图找一棵包含所有顶点的树使边的总权重最小。pythonimport heapq def prim_mst(graph, start0): Prim算法求最小生成树 贪心策略每次选择与已选集合相连的最短边 参数: graph: 邻接矩阵或邻接表 start: 起始顶点 返回: 最小生成树的边列表和总权重 n len(graph) visited [False] * n # 优先队列存储 (权重, 当前顶点, 父顶点) heap [(0, start, -1)] mst_edges [] total_weight 0 visited_count 0 while heap and visited_count n: weight, vertex, parent heapq.heappop(heap) if visited[vertex]: continue visited[vertex] True visited_count 1 total_weight weight if parent ! -1: mst_edges.append((parent, vertex, weight)) # 将所有邻接边加入堆 for neighbor, edge_weight in enumerate(graph[vertex]): if not visited[neighbor] and edge_weight 0: heapq.heappush(heap, (edge_weight, neighbor, vertex)) return mst_edges, total_weight # 测试代码 if __name__ __main__: # 邻接矩阵表示图 graph [ [0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9], [0, 5, 7, 9, 0] ] edges, total prim_mst(graph) print(f最小生成树总权重: {total}) print(选择的边:) for u, v, w in edges: print(f {u} -- {v} (权重: {w}))3.6 最短路径 - Dijkstra算法问题描述求单源最短路径图中边的权重非负。pythonimport heapq def dijkstra(graph, start): Dijkstra算法求单源最短路径 贪心策略每次选择距离源点最近的未访问顶点 参数: graph: 邻接表格式为 {顶点: [(邻接点, 权重), ...]} start: 起点 返回: 各顶点到起点的最短距离和前驱节点 n len(graph) dist [float(inf)] * n prev [-1] * n dist[start] 0 # 优先队列 (距离, 顶点) heap [(0, start)] while heap: current_dist, vertex heapq.heappop(heap) # 如果当前距离不是最小距离跳过 if current_dist dist[vertex]: continue # 遍历所有邻接边 for neighbor, weight in graph[vertex]: distance current_dist weight # 如果找到更短路径更新 if distance dist[neighbor]: dist[neighbor] distance prev[neighbor] vertex heapq.heappush(heap, (distance, neighbor)) return dist, prev def get_path(prev, target): 根据前驱数组重建路径 path [] current target while current ! -1: path.append(current) current prev[current] return path[::-1] # 反转 # 测试代码 if __name__ __main__: # 邻接表表示图 graph { 0: [(1, 4), (2, 2)], 1: [(3, 5)], 2: [(1, 1), (3, 8)], 3: [] } start 0 dist, prev dijkstra(graph, start) print(f从顶点 {start} 出发的最短距离:) for i, d in enumerate(dist): path get_path(prev, i) print(f 到 {i}: 距离{d}, 路径{path})四、贪心算法的常见应用场景应用领域具体问题贪心策略调度问题任务调度、区间调度最早截止时间优先、最短处理时间优先图论最小生成树、单源最短路径选择最小边、最近顶点数据压缩哈夫曼编码频率最小优先合并资源分配背包问题分数、缓存替换性价比最高、最近最少使用LRU网络路由路由选择、负载均衡跳数最少、延迟最低近似算法旅行商问题、集合覆盖最近邻、最大覆盖五、贪心算法的优缺点✅ 优点优点说明实现简单代码逻辑直观易于理解和实现效率高时间复杂度通常为 O(n) 或 O(n log n)空间省不需要存储所有子问题的解适合在线算法可以在数据流中逐步做出决策❌ 缺点缺点说明不一定能得到全局最优局部最优不一定是全局最优需要证明贪心选择性质使用前必须证明贪心策略的正确性适用范围有限不是所有问题都满足贪心选择性质六、判断是否使用贪心的技巧6.1 快速判断清单text□ 问题是否具有最优子结构 □ 问题是否具有贪心选择性质 □ 是否可以证明局部最优能导致全局最优 □ 是否可以用反例推翻贪心策略6.2 常见反例模式python# 1. 0-1背包问题不能用贪心 # 容量: 10 # 物品: (重量, 价值) [(6, 10), (5, 8), (5, 8)] # 贪心: 按价值/重量选选(6,10) → 总价值10 ❌ # 最优: 选两个(5,8) → 总价值16 ✅ # 2. 最长路径问题不能用贪心 # 贪心选最大边可能导致死路 # 3. 图着色问题不能用贪心 # 贪心选色可能用更多颜色七、面试常见问题Q1: 贪心算法和动态规划的区别A: 贪心是鼠目寸光只选当前最优动态规划是高瞻远瞩考虑所有可能。贪心更快但适用范围小。Q2: 什么时候贪心算法能得到最优解A: 当问题同时满足贪心选择性质和最优子结构性质时。Q3: 哪些经典问题必须用贪心A: 活动选择、哈夫曼编码、最小生成树Prim/Kruskal、Dijkstra最短路径。八、总结口诀text贪心算法不复杂 每步都选最优它。 活动选择看结尾 背包分数算单价。 哈夫曼树频最小 Prim Dijkstra图当家。 局部最优不一定 证明性质再用它。