贪心算法 (Greedy Algorithm)

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

一句话总结：目光短浅，只看眼前。

贪心 vs 动态规划

• 动态规划: 会考虑全局，记录所有子问题的解，并在最后通过选择来达到全局最优。
• 贪心: 不考虑整体，只做局部最优决策。一旦做出选择，就无法回退。

注意: 贪心算法并不总能得到全局最优解。只有当问题满足 "贪心选择性质" 时才有效。

典型案例 1：找零钱问题

题目：假设你有面值为 25, 10, 5, 1 的硬币。需要找零 amount，求最少需要几枚硬币？

策略：为了让硬币数量最少，我们应该尽可能多地使用面值大的硬币。

def change_coins(amount):
    coins = [25, 10, 5, 1]
    count = 0

    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            print(f"使用一枚 {coin}")

    return count

print(f"总共: {change_coins(41)}")
# 25, 10, 5, 1 -> 4枚 (贪心成功)

贪心的局限性： 如果硬币面值是 [25, 20, 1]，找 40。

• 贪心策略：25 + 1 + ... + 1 (16 枚) -> 失败
• 最优策略：20 + 20 (2 枚) 在这种情况下，必须使用动态规划。

典型案例 2：区间调度 (Interval Scheduling)

题目：给定一系列会议的开始和结束时间 [[s1, e1], [s2, e2], ...]，求一个人最多能参加多少个不重叠的会议？

策略：

1. 优先选持续时间短的？❌ (可能在中间阻断两个长会议)
2. 优先选开始时间早的？❌ (可能一个会议开一天)
3. 优先选结束时间早的！✅
   • 结束得越早，留给后面的时间就越多，能容纳的会议就越多。

def interval_scheduling(intervals):
    if not intervals: return 0

    # 按结束时间升序排序
    intervals.sort(key=lambda x: x[1])

    count = 1
    end_time = intervals[0][1]

    for i in range(1, len(intervals)):
        start_time = intervals[i][0]
        # 如果当前会议开始时间 >= 上个会议结束时间
        if start_time >= end_time:
            count += 1
            end_time = intervals[i][1]

    return count

tests = [[1, 3], [2, 4], [3, 5]]
print(interval_scheduling(tests)) # 2 ([1,3], [3,5])

本章小结

贪心算法效率极高（通常是 \(O(n \log n)\) 排序 + \(O(n)\) 遍历），但证明其正确性往往很难。 在做题时，如果发现局部最优能推导全局最优，或者可以直接举反例（如找零钱特例）来验证是否可用贪心。

---

下一章：搜索算法