玩转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': ''}

执行流程

1. 创建一个优先队列priorityQueue，将所有字符及其频率作为节点加入队列，并按频率从小到大排序。
2. 当队列中有多于一个节点时：
   • 弹出两个频率最小的节点left和right。
   • 创建一个新节点merged，其频率为left和right之和，并将left和right作为子节点。
   • 将新节点加入优先队列。
3. 返回队列中唯一的节点，即哈夫曼树的根节点。
4. 使用递归遍历哈夫曼树，为每个字符生成编码，并存储在字典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}

执行流程

1. 初始化所有顶点到源点的距离为无穷大，源点到自身的距离为0。
2. 创建一个优先队列priorityQueue，将源点及其距离（0）加入队列。
3. 当优先队列非空时：
   • 弹出距离最小的顶点currentVertex及其距离currentDistance。
   • 如果弹出的距离大于当前已知的距离，则跳过该顶点。
   • 对于当前顶点的每个邻居：
     • 计算通过当前顶点到达邻居的距离。
     • 如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。
4. 返回所有顶点到源点的距离。

应用场景

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)]

执行流程

1. 初始化并查集UnionFind。
2. 对所有边按照权重从小到大排序。
3. 对于每条边：
   • 如果边的两个顶点不在同一个集合中，则将它们合并，并添加到结果中。
4. 返回结果，即最小生成树的所有边。

应用场景

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}

执行流程

1. 初始化所有顶点到起始顶点的距离为无穷大，起始顶点到自身的距离为0。
2. 创建一个优先队列priorityQueue，将起始顶点及其距离（0）加入队列。
3. 当优先队列非空时：
   • 弹出距离最小的顶点currentVertex及其距离currentDistance。
   • 如果弹出的距离大于当前已知的距离，则跳过该顶点。
   • 对于当前顶点的每个邻居：
     • 计算通过当前顶点到达邻居的距离。
     • 如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。
4. 返回所有顶点到起始顶点的距离。

应用场景

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 

执行流程

1. 初始化max_current和max_global为数组的第一个元素。
2. 对于数组中的每个元素：
   • 更新max_current为当前元素与当前元素加上前一个max_current的最大值。
   • 如果max_current大于max_global，则更新max_global。
3. 返回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 

执行流程

1. 创建一个物品列表items，包含物品的价值和重量。
2. 对物品列表按照价值/重量比降序排序。
3. 初始化总价值total_value为0。
4. 对于每个物品：
   • 如果物品的重量小于等于剩余容量，则将物品的价值加到总价值，并减少剩余容量。
   • 如果物品的重量大于剩余容量，则将物品的部分价值加到总价值，并结束循环。
5. 返回总价值，即分数背包问题的最优解。

应用场景

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

算法复杂度

复杂度类型	时间复杂度	空间复杂度
分数背包	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)

执行流程

1. 将硬币面值列表coins按照面值从大到小排序。
2. 初始化硬币计数count为0，余数remainder为待找零的金额。
3. 对于每种硬币面值：
   • 计算当前硬币可以用于找零的次数，并累加到count。
   • 更新余数remainder为剩余待找零的金额。
   • 如果余数为0，则说明已经找到最优解，结束循环。
4. 如果循环结束后余数仍不为0，则说明无法用给定的硬币面值凑成指定金额，返回-1；否则返回硬币计数count。

应用场景

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

算法复杂度

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

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