当前位置：首页 > article >正文

python 实现贪心算法（Greedy Algorithm）

article 2025/1/7 23:49:15

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

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

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

def activity_selection(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    selected = []
    last_end = -1
    
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return 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）

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

import heapq

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(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 = left
        merged.right = right
        heapq.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] = prefix
        build_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 算法的实现。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_edge(self, u, v, w):
        self.edges.append((u, v, w))
    
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return 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] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1
    
    def kruskal_mst(self):
        result = []
        self.edges.sort(key=lambda x: x[2])  # 按权重排序
        parent = [i for i in range(self.V)]
        rank = [0] * self.V
        for 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）

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

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    result = []
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return 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]