贪心算法详解：原理、代码与示例

贪心算法解决什么问题

贪心算法针对的是优化问题：安排最多的活动、用最少的硬币、搭建成本最低的网络、把文件压缩成最少的比特。贪心算法不会穷举所有组合，而是先对选项排序或设定优先级，然后在每一步都坚定地选择最好的那个。时间复杂度通常是 O(n log n)，往往就是排序的开销。

难点不在代码，而在证明。许多看上去自然的贪心规则其实是错的，所以你要么证明规则正确，要么用暴力解法对它进行测试。

用大白话讲思路

1. 找一条给选项排序的规则，例如“结束时间最早的优先”或“最轻的边优先”。
2. 按这条规则对选项排序，或把它们放进优先队列。
3. 依次检查各选项，只要约束仍然允许，就选取它。
4. 绝不撤销已做的选择。

当两个性质同时成立时，贪心算法才是正确的。贪心选择性质：存在某个最优解包含第一步的贪心选择。最优子结构：做出该选择后，剩下的部分是同一问题的更小实例。常见的证明方法是交换论证：取任意一个最优解，证明把其中某个选择换成贪心选择并不会使结果变差。

实例：区间调度

你只有一间会议室，收到以下申请（开始, 结束）：A (1, 4)、B (3, 5)、C (0, 6)、D (5, 7)、E (3, 9)、F (5, 9)、G (6, 10)、H (8, 11)。要预订尽可能多的互不重叠的会议。正确的贪心规则是：在开始时间不早于上一场已预订会议结束时间的会议中，始终选择结束最早的那个。

结果：A、D、H，共三场会议，这已是最大值。原理：结束最早的会议为其他所有会议留下最多的时间，所以把任意最优日程中的第一场会议换成它，永远不会引起冲突。

Python 实现

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

第二个经典例子是分数背包：当可以只取物品的一部分时，按单位重量的价值从高到低取物品是最优的。

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

贪心失效时：反例

时间与空间复杂度

空间复杂度通常是 O(n)，用于排序后的副本或堆。如果输入已经有序，许多贪心算法只需 O(n)。

何时使用贪心及实际应用

• 当你能证明贪心选择性质，或可以接受快速的近似解时，使用贪心。否则请使用动态规划或回溯。
• 压缩：哈夫曼编码通过反复合并出现频率最低的两个符号，构造出最优前缀码；DEFLATE（ZIP、gzip、PNG）等格式内部就用到了它。
• 网络：最小生成树（Kruskal、Prim）和最短路径路由（Dijkstra）。
• 调度：最早截止时间优先，以及预订房间或机器。
• 近似算法：对集合覆盖问题，贪心规则“选择覆盖最多未覆盖元素的集合”并不最优，但可以保证与最优解相差不超过一个对数因子。
• 面试题：跳跃游戏、加油站、分发饼干、无重叠区间、用最少数量的箭引爆气球、任务调度器。