算法学习6——贪心算法

什么是贪心算法？

贪心算法是一种在每一步选择中都采取当前状态下最优或最有利的选择的算法。其核心思想是通过一系列局部最优选择来达到全局最优解。贪心算法广泛应用于各种优化问题，如最短路径、最小生成树、背包问题等。

贪心算法的特点

1. 局部最优选择：每一步都做出在当前情况下最优的选择。
2. 无后效性：一旦某个状态被确定，就不会再被改变或回溯。
3. 逐步构造解决方案：通过一系列的选择逐步构建出最终的解决方案。

经典例子及其Python实现

1. 活动选择问题

问题描述：给定一组活动，每个活动有一个开始时间和结束时间，要求选择尽可能多的互不重叠的活动。

贪心策略：每次选择结束时间最早且不与已选择活动重叠的活动。

实现过程：

1. 将所有活动按结束时间排序。
2. 依次选择结束时间最早且不与已选择活动重叠的活动。

Python代码：

def activity_selection(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    
    # 选择活动
    selected_activities = [activities[0]]
    last_end_time = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end_time:
            selected_activities.append((start, end))
            last_end_time = end
    
    return selected_activities

# 示例
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))

2. 背包问题

问题描述：给定一组物品，每个物品有重量和价值，要求在总重量不超过背包容量的前提下，使背包中的物品总价值最大。

贪心策略：每次选择单位重量价值最高的物品。

实现过程：

1. 将所有物品按单位重量价值排序。
2. 依次选择单位重量价值最高且不超过剩余容量的物品。

Python代码：

def 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:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break
    
    return total_value

# 示例
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
print(knapsack(items, capacity))

3. 哈夫曼编码

问题描述：给定一组字符及其出现频率，要求构造一个前缀码，使得编码后的字符串长度最短。

贪心策略：每次选择出现频率最低的两个字符合并，构造哈夫曼树。

实现过程：

1. 将所有字符按频率构造最小堆。
2. 依次取出频率最低的两个节点，合并后重新插入堆中。
3. 重复上述过程，直到所有节点合并为一棵树。

Python代码：

import heapq

def huffman_encoding(frequencies):
    heap = [[weight, [symbol, ""]] for symbol, 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': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
print(huffman_encoding(frequencies))

结论

贪心算法通过局部最优选择来构建全局最优解，简单高效，适用于多种优化问题。然而，贪心算法并不总是能得到最优解，因此在使用前需要确保问题满足贪心选择性质。