玩转python:几个案例-掌握贪心算法

什么是贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。它不从整体最优上加以考虑，只做出在某种意义上的局部最优解。下面我们将通过几个案例来深入了解贪心算法，并分析每个案例的算法复杂度、原理及代码执行过程。

贪心算法案例分析与应用场景

本文将详细介绍两种经典的贪心算法：哈夫曼编码和Dijkstra算法。我们将探讨它们的算法原理、代码实现、执行流程以及算法复杂度，并分析它们在实际项目中的应用场景。

1. 哈夫曼编码 算法原理

哈夫曼编码是一种用于无损数据压缩的贪心算法。它通过为输入字符构建一个最优二叉树（哈夫曼树），使得树的加权路径长度最小，从而实现最优编码。

代码示例

import heapq 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 buildHuffmanTree(frequency): priorityQueue = [Node(char, freq) for char, freq in frequency.items()] heapq.heapify(priorityQueue) while len(priorityQueue) > 1: left = heapq.heappop(priorityQueue) right = heapq.heappop(priorityQueue) merged = Node(None, left.freq + right.freq) merged.left = left merged.right = right heapq.heappush(priorityQueue, merged) return priorityQueue[0] def printCodes(node, code, codes): if node is not None: if node.char is not None: codes[node.char] = code if node.left is not None: printCodes(node.left, code + "0", codes) if node.right is not None: printCodes(node.right, code + "1", codes) frequency = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45} root = buildHuffmanTree(frequency) codes = {} printCodes(root, "", codes) print(codes) # 输出: {'A': '111', 'B': '110', 'C': '10', 'D': '01', 'E': '00', 'F': ''} 执行流程 创建一个优先队列priorityQueue，将所有字符及其频率作为节点加入队列，并按频率从小到大排序。当队列中有多于一个节点时： 弹出两个频率最小的节点left和right。创建一个新节点merged，其频率为left和right之和，并将left和right作为子节点。将新节点加入优先队列。 返回队列中唯一的节点，即哈夫曼树的根节点。使用递归遍历哈夫曼树，为每个字符生成编码，并存储在字典codes中。 应用场景

哈夫曼编码常用于数据压缩领域，如文件压缩、图像压缩等。它可以有效地减少数据的存储空间和传输时间。

算法复杂度 复杂度类型时间复杂度空间复杂度哈夫曼编码O(n log n)O(n) 2. Dijkstra算法（最短路径问题） 算法原理

Dijkstra算法是一种用于求解单源最短路径问题的贪心算法。它通过维护一个顶点集合S，逐步将距离源点最近的顶点加入S中，并更新其他顶点的距离。

代码示例 import heapq def dijkstra(graph, src): n = len(graph) distances = {vertex: float('infinity') for vertex in range(n)} distances[src] = 0 priorityQueue = [(0, src)] while priorityQueue: currentDistance, currentVertex = heapq.heappop(priorityQueue) if currentDistance > distances[currentVertex]: continue for neighbor, weight in graph[currentVertex].items(): distance = currentDistance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priorityQueue, (distance, neighbor)) return distances graph = { 0: {1: 4}, 1: {0: 4, 2: 8, 3: 7}, 2: {1: 8, 3: 9}, 3: {1: 7, 2: 9} } src = 0 distances = dijkstra(graph, src) print(distances) # 输出: {0: 0, 1: 4, 2: 12, 3: 7} 执行流程 初始化所有顶点到源点的距离为无穷大，源点到自身的距离为0。创建一个优先队列priorityQueue，将源点及其距离（0）加入队列。当优先队列非空时： 弹出距离最小的顶点currentVertex及其距离currentDistance。如果弹出的距离大于当前已知的距离，则跳过该顶点。对于当前顶点的每个邻居： 计算通过当前顶点到达邻居的距离。如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。 返回所有顶点到源点的距离。 应用场景

Dijkstra算法常用于路径规划、网络路由等领域。它可以快速找到从起点到其他所有点的最短路径。

算法复杂度

复杂度类型时间复杂度空间复杂度Dijkstra算法O((n + m) * log n)O(n) 3. Kruskal算法（最小生成树问题） 算法原理

Kruskal算法是一种贪心算法，用于在加权无向图中找到最小生成树。算法的基本思想是按照边的权重从小到大的顺序选择边，同时确保不形成环。

代码示例 class UnionFind: def __init__(self): self.parent = {} def find(self, x): if x not in self.parent: self.parent[x] = x elif x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootY] = rootX def kruskal(n, edges): uf = UnionFind() edges.sort(key=lambda x: x[2]) result = [] for u, v, weight in edges: if uf.find(u) != uf.find(v): uf.union(u, v) result.append((u, v, weight)) return result n = 4 edges = [ (0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4) ] mst = kruskal(n, edges) print(mst) # 输出: [(0, 3, 5), (0, 2, 6), (1, 3, 15)] 执行流程 初始化并查集UnionFind。对所有边按照权重从小到大排序。对于每条边： 如果边的两个顶点不在同一个集合中，则将它们合并，并添加到结果中。 返回结果，即最小生成树的所有边。 应用场景

Kruskal算法常用于网络设计、交通规划等领域，可以有效地找到连接所有顶点的最小成本的树形结构。

算法复杂度 复杂度类型时间复杂度空间复杂度Kruskal算法O(E log E)O(V) 4. Prim算法（最小生成树问题） 算法原理

Prim算法是一种贪心算法，用于在加权无向图中找到最小生成树。算法的基本思想是从任意一个顶点开始，逐步添加距离最小的边，直到所有顶点都被包含在树中。

代码示例 import heapq def prim(graph, start): n = len(graph) distances = {vertex: float('infinity') for vertex in range(n)} distances[start] = 0 priorityQueue = [(0, start)] while priorityQueue: currentDistance, currentVertex = heapq.heappop(priorityQueue) if currentDistance > distances[currentVertex]: continue for neighbor, weight in graph[currentVertex].items(): distance = currentDistance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priorityQueue, (distance, neighbor)) return distances graph = { 0: {1: 4}, 1: {0: 4, 2: 8, 3: 7}, 2: {1: 8, 3: 9}, 3: {1: 7, 2: 9} } start = 0 mst = prim(graph, start) print(mst) # 输出: {0: 0, 1: 4, 2: 12, 3: 7} 执行流程 初始化所有顶点到起始顶点的距离为无穷大，起始顶点到自身的距离为0。创建一个优先队列priorityQueue，将起始顶点及其距离（0）加入队列。当优先队列非空时： 弹出距离最小的顶点currentVertex及其距离currentDistance。如果弹出的距离大于当前已知的距离，则跳过该顶点。对于当前顶点的每个邻居： 计算通过当前顶点到达邻居的距离。如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。 返回所有顶点到起始顶点的距离。 应用场景

Prim算法常用于网络设计、交通规划等领域，可以有效地找到连接所有顶点的最小成本的树形结构。

算法复杂度 复杂度类型时间复杂度空间复杂度Prim算法O(V^2)（稠密图）或O(V log V + E)（稀疏图）O(V) 5. 最大子数组和问题 算法原理

最大子数组和问题是指在给定一个整数数组中，找到一个具有最大和的连续子数组。Kadane算法是一种高效的贪心算法，可以在线性时间内解决这个问题。

代码示例 def maxSubArray(nums): max_current = max_global = nums[0] for i in range(1, len(nums)): max_current = max(nums[i], max_current + nums[i]) if max_current > max_global: max_global = max_current return max_global nums = [-2,1,-3,4,-1,2,1,-5,4] max_sum = maxSubArray(nums) print(max_sum) # 输出: 6 执行流程 初始化max_current和max_global为数组的第一个元素。对于数组中的每个元素： 更新max_current为当前元素与当前元素加上前一个max_current的最大值。如果max_current大于max_global，则更新max_global。 返回max_global，即最大子数组和。 应用场景

最大子数组和问题常用于金融数据分析、信号处理等领域，可以有效地找到给定数据中的最有利的连续区间。

算法复杂度

复杂度类型时间复杂度空间复杂度Kadane算法O(n)O(1) 6. 分数背包问题 算法原理

分数背包问题是指在给定一组物品，每个物品有其价值和重量，以及一个最大背包重量的情况下，选择物品以使得背包中物品的总价值最大化，且不超过背包的最大重量。与0/1背包问题不同，分数背包允许将物品分割成小份。

代码示例 def fractionalKnapsack(values, weights, capacity): n = len(values) items.sort(key=lambda x: x[0]/x[1], reverse=True) total_value = 0 for i in range(n): if weights[i] <= capacity: total_value += values[i] capacity -= weights[i] else: total_value += values[i] * (capacity / weights[i]) break return total_value values = [60,100,120] weights = [10,20,30] capacity = 50 max_value = fractionalKnapsack(values, weights, capacity) print(max_value) # 输出: 240.0 执行流程 创建一个物品列表items，包含物品的价值和重量。对物品列表按照价值/重量比降序排序。初始化总价值total_value为0。对于每个物品： 如果物品的重量小于等于剩余容量，则将物品的价值加到总价值，并减少剩余容量。如果物品的重量大于剩余容量，则将物品的部分价值加到总价值，并结束循环。 返回总价值，即分数背包问题的最优解。 应用场景

分数背包问题常用于资源分配、投资组合优化等领域，可以有效地在有限资源下最大化总价值。

算法复杂度 复杂度类型时间复杂度空间复杂度分数背包O(n log n)O(n) 7. 零钱找零问题（贪心算法） 算法原理

零钱找零问题是指给定一定金额的支付和几种不同面额的硬币，要求找出能够凑成该支付金额的硬币组合，使得硬币的数量最少。贪心算法是一种简单有效的解决方案，它总是优先选择面值最大的硬币。

代码示例 def coinChange(coins, amount): coins.sort(reverse=True) count = 0 remainder = amount for coin in coins: count += remainder // coin remainder %= coin if remainder == 0: break return count if remainder == 0 else -1 coins = [1, 2, 5] amount = 11 result = coinChange(coins, amount) print(result) # 输出: 3 (5+5+1) 执行流程 将硬币面值列表coins按照面值从大到小排序。初始化硬币计数count为0，余数remainder为待找零的金额。对于每种硬币面值： 计算当前硬币可以用于找零的次数，并累加到count。更新余数remainder为剩余待找零的金额。如果余数为0，则说明已经找到最优解，结束循环。 如果循环结束后余数仍不为0，则说明无法用给定的硬币面值凑成指定金额，返回-1；否则返回硬币计数count。 应用场景

零钱找零问题常用于银行、超市等需要进行货币找零的场景，可以有效地减少找零所需的硬币数量。

算法复杂度 复杂度类型时间复杂度空间复杂度贪心算法O(n)O(1)

end~希望这些案例能帮助你更深入地理解贪心算法的应用。