python 实现贪心算法（Greedy Algorithm）

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前最优的选择，希望通过局部最优解达到全局最优解的算法设计方法。以下是使用Python实现贪心算法解决几个经典问题的示例：

1. 活动选择问题（Activity Selection Problem）

活动选择问题是选择最多的互不冲突的活动。

python">def activity_selection(activities):# 按结束时间排序activities.sort(key=lambda x: x[1])selected = []last_end = -1for start, end in activities:if start >= last_end:selected.append((start, end))last_end = endreturn selected# 示例
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(activity_selection(activities))
# 输出: [(1, 4), (5, 7), (8, 11), (12, 16)]

2. 霍夫曼编码（Huffman Coding）

霍夫曼编码是一种用于数据压缩的贪心算法。

python">import heapqclass HuffmanNode:def __init__(self, char, freq):self.char = charself.freq = freqself.left = Noneself.right = Nonedef __lt__(self, other):return self.freq < other.freqdef build_huffman_tree(freq_map):heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]heapq.heapify(heap)while len(heap) > 1:left = heapq.heappop(heap)right = heapq.heappop(heap)merged = HuffmanNode(None, left.freq + right.freq)merged.left = leftmerged.right = rightheapq.heappush(heap, merged)return heapq.heappop(heap)def build_huffman_codes(node, prefix="", code_map=None):if code_map is None:code_map = {}if node:if node.char:code_map[node.char] = prefixbuild_huffman_codes(node.left, prefix + "0", code_map)build_huffman_codes(node.right, prefix + "1", code_map)return code_map# 示例
freq_map = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
huffman_tree = build_huffman_tree(freq_map)
huffman_codes = build_huffman_codes(huffman_tree)
print(huffman_codes)
# 输出: {'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111'}

3. 最小生成树（MST, Minimum Spanning Tree）

最小生成树问题可以通过 Kruskal 或 Prim 算法解决。以下是 Kruskal 算法的实现。

python">class Graph:def __init__(self, vertices):self.V = verticesself.edges = []def add_edge(self, u, v, w):self.edges.append((u, v, w))def find(self, parent, i):if parent[i] == i:return ireturn self.find(parent, parent[i])def union(self, parent, rank, x, y):xroot = self.find(parent, x)yroot = self.find(parent, y)if rank[xroot] < rank[yroot]:parent[xroot] = yrootelif rank[xroot] > rank[yroot]:parent[yroot] = xrootelse:parent[yroot] = xrootrank[xroot] += 1def kruskal_mst(self):result = []self.edges.sort(key=lambda x: x[2])  # 按权重排序parent = [i for i in range(self.V)]rank = [0] * self.Vfor u, v, w in self.edges:x = self.find(parent, u)y = self.find(parent, v)if x != y:result.append((u, v, w))self.union(parent, rank, x, y)return result# 示例
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print(g.kruskal_mst())
# 输出: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

4. 硬币找零问题（Coin Change Problem）

硬币找零问题是使用最少数量的硬币凑成指定金额。

python">def coin_change(coins, amount):coins.sort(reverse=True)  # 从大到小排序result = []for coin in coins:while amount >= coin:result.append(coin)amount -= coinreturn result if amount == 0 else None# 示例
coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
amount = 93
print(coin_change(coins, amount))
# 输出: [50, 20, 20, 2, 1]