一、什么是贪心算法

想象你在自助餐厅拿食物：每次只拿当前看起来最好吃的那个菜，而不考虑后面可能出现更美味的菜品。贪心算法就是这样，每一步都选择当下看起来最优的选项，希望最终结果也是最优的。它的核心思想是“局部最优可能导致全局最优”，但要注意，这个“可能”是关键。

二、贪心算法适用场景

1. 问题具有贪心选择性质

比如找零钱问题：用最少的硬币凑出指定金额。假设硬币有1元、5元、10元，要凑18元。贪心策略是每次选最大面额：

# 技术栈：Python  
def greedy_coin_change(amount, coins=[10, 5, 1]):
    result = []
    for coin in coins:
        while amount >= coin:  # 只要当前硬币能用就用
            amount -= coin
            result.append(coin)
    return result

print(greedy_coin_change(18))  # 输出：[10, 5, 1, 1, 1]

注释：这个例子中，每次选最大面额硬币，最终结果确实是最优解。但若硬币面额是1元、4元、5元，要凑8元，贪心会给出[5,1,1,1]，而实际最优是[4,4]。

2. 问题可以分解为子问题

比如活动选择问题：在一堆时间不冲突的活动中选最多场次。贪心策略是每次选结束最早的活动：

# 技术栈：Python  
activities = [(1,4), (3,5), (0,6), (5,7), (8,9)]
sorted_activities = sorted(activities, key=lambda x: x[1])  # 按结束时间排序
selected = [sorted_activities[0]]
for start, end in sorted_activities[1:]:
    if start >= selected[-1][1]:  # 当前活动开始时间不冲突
        selected.append((start, end))
print(selected)  # 输出：[(1,4), (5,7), (8,9)]

注释：这里局部最优（选最早结束）确实保证了全局最优（最多活动场次）。

三、贪心算法的优缺点

优点

  • 高效：通常时间复杂度是O(n)或O(n log n)，比如排序后线性处理。
  • 简单：逻辑直观，代码容易实现。

缺点

  • 不一定全局最优：如前面硬币问题的反例。
  • 依赖问题特性：必须证明局部最优能推导全局最优，否则可能翻车。

四、注意事项

  1. 验证贪心策略的正确性：比如背包问题中，若物品可分割（分数背包），贪心有效；若不可分割（0-1背包），则无效。
  2. 边界条件处理：比如硬币问题中若amount=0或硬币面额不包含1元时需特殊处理。
  3. 与动态规划对比：动态规划会保存中间状态，贪心则“一往无前”。

五、经典应用场景

  1. 哈夫曼编码：用最短二进制编码表示高频字符。
  2. Dijkstra最短路径：每次选当前最近的节点。
  3. 最小生成树（Prim/Kruskal）：逐步连接最小权重的边。

六、总结

贪心算法像生活中的“及时行乐”，适合那些“当前最优能推导全局最优”的问题。用之前务必验证策略的正确性，否则可能陷入局部最优的陷阱。当问题具备贪心选择性质时，它会是你的高效武器；否则，可能需要动态规划等其他方法。