贪心算法

贪心算法:

贪心算法（Greedy Algorithm）是一种逐步构建解决方案的算法。每一步选择中，贪心算法都做出局部最优的选择，以期最终获得全局最优解。

原理

1. 将问题分解为一系列子问题。

2. 每次选择当前子问题的局部最优解，而不考虑未来的后果。

3. 重复以上步骤，直到问题解决。

贪心算法适用于贪心选择性质和最优子结构的问题：

• 贪心选择性质：通过局部最优选择可以得到问题的全局最优解。

• 最优子结构：问题的最优解包含其子问题的最优解。

常见贪心算法问题及Python示例

1. 活动选择问题

问题：给定一组活动，每个活动有开始时间和结束时间，选择尽可能多的互不冲突的活动。

示例代码：

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]  # 选择第一个活动
    for i in range(1, len(activities)):
        if activities[i][0] >= selected[-1][1]:  # 如果不冲突
            selected.append(activities[i])
    return selected
​
# 测试
activities = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 9)]
print(activity_selection(activities))

用途：会议安排、任务调度等。

2. 背包问题（分数型）

问题：有一个容量固定的背包，若物品可以分割，选择最有价值的装入方案。

示例代码：

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1] / x[0], reverse=True)  # 按单位价值排序
    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

# 测试
items = [(10, 60), (20, 100), (30, 120)]  # (重量, 价值)
capacity = 50
print(fractional_knapsack(items, capacity))

用途：资源分配、库存优化等。

3. 最小生成树（Prim/Kruskal算法）

问题：在加权图中，找到包含所有顶点的最小生成树。

示例代码（Kruskal算法）：

def kruskal(graph):
    parent = {}
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    
    def union(u, v):
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            parent[root_u] = root_v
    
    edges = sorted(graph['edges'], key=lambda x: x[2])  # 按权重排序
    for node in graph['vertices']:
        parent[node] = node
    
    mst = []
    for u, v, weight in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))
    return mst

# 测试
graph = {
    'vertices': ['A', 'B', 'C', 'D', 'E'],
    'edges': [
        ('A', 'B', 1), ('A', 'C', 3), ('B', 'C', 1),
        ('B', 'D', 4), ('C', 'D', 2), ('D', 'E', 5)
    ]
}
print(kruskal(graph))

用途：网络设计（如电网、路网）。

4. 赫夫曼编码

问题：给定一组字符及其频率，构建一棵赫夫曼树以实现最优编码。

示例代码：

import heapq

def huffman_encoding(frequencies):
    heap = [[weight, [char, ""]] for char, weight in frequencies.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

# 测试
frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
print(huffman_encoding(frequencies))

用途：数据压缩（如JPEG、MP3、ZIP）。

贪心算法用途

1. 路径规划：如Dijkstra算法计算最短路径。

2. 资源优化：如任务分配、库存管理。

3. 数据压缩：如赫夫曼编码。

4. 网络设计：如最小生成树。

贪心算法适用于简单、局部最优可解全局问题，但不适用于需要穷举或动态规划的问题。