贪心：每一步都选当前最好

先看一个看着很对的策略

找零钱。手里有 1 元、5 元、10 元、25 元的硬币，要凑出 63 元，怎么让硬币枚数最少？

绝大多数人会这么做：先看 25 元能用几枚，再用 10 元，再用 5 元，最后用 1 元。 这就是贪心——每一步都挑当前面额最大的那枚。

这个策略对这套面额完全正确。金额从 1 试到 199，贪心和真正的最优解一枚都不差：

def greedy_coins(coins, amount):
    """每步都挑当前能用的最大面额。"""
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None


def best_coins(coins, amount):
    """动态规划：真正的最少枚数。"""
    INF = float('inf')
    dp = [0] + [INF] * amount
    for v in range(1, amount + 1):
        for c in coins:
            if c <= v and dp[v - c] + 1 < dp[v]:
                dp[v] = dp[v - c] + 1
    return dp[amount]


bad = [v for v in range(1, 200)
       if len(greedy_coins([1, 5, 10, 25], v)) != best_coins([1, 5, 10, 25], v)]
print('  面额 [1, 5, 10, 25]，金额 1 到 199：贪心与最优不一致的有', len(bad), '个')
print('  金额 63 贪心给', greedy_coins([1, 5, 10, 25], 63),
      '共', len(greedy_coins([1, 5, 10, 25], 63)), '枚')

  面额 [1, 5, 10, 25]，金额 1 到 199：贪心与最优不一致的有 0 个
  金额 63 贪心给 [25, 25, 10, 1, 1, 1] 共 6 枚

跑起来一次都没错，你会很自然地认为「找零钱就该这么贪」。

换一套面额，它立刻错。 面额改成 1 元、3 元、4 元：

coins = [1, 3, 4]
for v in range(1, 31):
    g = greedy_coins(coins, v)
    b = best_coins(coins, v)
    if len(g) != b:
        print(f'  金额 {v}: 贪心 {g} 共 {len(g)} 枚，最优 {b} 枚')

  金额 6: 贪心 [4, 1, 1] 共 3 枚，最优 2 枚
  金额 10: 贪心 [4, 4, 1, 1] 共 4 枚，最优 3 枚
  金额 14: 贪心 [4, 4, 4, 1, 1] 共 5 枚，最优 4 枚
  金额 18: 贪心 [4, 4, 4, 4, 1, 1] 共 6 枚，最优 5 枚
  金额 22: 贪心 [4, 4, 4, 4, 4, 1, 1] 共 7 枚，最优 6 枚
  金额 26: 贪心 [4, 4, 4, 4, 4, 4, 1, 1] 共 8 枚，最优 7 枚
  金额 30: 贪心 [4, 4, 4, 4, 4, 4, 4, 1, 1] 共 9 枚，最优 8 枚

凑 6 元：贪心先拿最大的 4，剩 2 元只能拿两个 1，一共 3 枚。最优解是 3 + 3，两枚。

这就是贪心最要紧的一件事：「每一步都选当前最好」这个想法本身不保证结果最好。 它有时对，有时错，而错的时候答案看起来一样合情合理——上面每一行的贪心解都能凑出那个金额，只是枚数多。

贪心选择性质

一个策略要算贪心算法，光「每步选当前最好」不够，还得额外满足一条：

贪心选择性质：每一步选的那个「当前最好」，一定存在于某个全局最优解里。

找零的 1/5/10/25 满足它——最优解里总能找到一个含最大面额的。1/3/4 不满足：凑 6 元的最优解 3+3 里根本没有 4，而贪心第一步就把 4 拿走了，之后再补救也补不回来。

一个贪心策略对不对，跟代码写法无关，只跟这条性质成不成立有关。所以判断一道题能不能贪心，不是看它像不像贪心题，而是要问：我现在选的这个，会不会堵死后面的路？ 会，就不能贪。

交换论证的套路

那条性质怎么证明？竞赛里最常用的办法叫交换论证，套路是三句话：

1. 假设存在一个最优解，它跟我贪心选的不一样。
2. 把它里面第一个和我不同的选择，换成我贪心的那个选择。换完之后，剩下的部分照样接得上，总代价没变差。
3. 于是存在一个也含我贪心这个选择的最优解。一步一步换下去，最优解就变成了贪心解——贪心解就是最优解。

关键是第 2 步那个「换」。你要说明的是：换掉之后不会变坏，也不会接不上。 这两点说清楚了，论证就成立了。

拿区间调度（下面那节）举例，交换论证长这样：

• 设最优解第一个区间是 B，贪心选的第一个区间是 A（结束时间最早的那个）。因为 A 的结束时间不晚于任何区间，所以 A 的结束时间也不晚于 B。
• 把最优解里的 B 换成 A。A 结束得更早，剩下的区间只会更容易接上，不会变少。
• 所以存在一个以 A 开头的最优解。对剩下的区间重复这个论证，贪心解就等于最优解。

三句话，不用公式。写不出这三句话，就说明你还没想清楚为什么能贪。

区间调度怎么排

区间调度：给一堆区间，选出最多的、互不重叠的区间。

贪心策略是：把所有区间按结束时间从早到晚排，然后扫一遍，能放就放。

def pick_by(ivs, key):
    """按 key 排序后扫一遍，跟上一个选的接得上就选。"""
    chosen = []
    last_end = None
    for a, b in sorted(ivs, key=key):
        if last_end is None or a >= last_end:
            chosen.append((a, b))
            last_end = b
    return chosen


def brute_max(ivs):
    """枚举所有子集，找出最多能选几个互不重叠的区间（区间少的时候才能用）。"""
    best = 0
    n = len(ivs)
    for mask in range(1 << n):
        cnt = bin(mask).count('1')
        if cnt <= best:
            continue
        sel = sorted(ivs[i] for i in range(n) if mask >> i & 1)
        if all(sel[i][1] <= sel[i + 1][0] for i in range(len(sel) - 1)):
            best = cnt
    return best


ivs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (12, 14), (2, 6)]
for name, key in [('按结束时间排', lambda t: (t[1], t[0])),
                  ('按开始时间排', lambda t: (t[0], t[1])),
                  ('按区间长度排', lambda t: (t[1] - t[0], t[0]))]:
    got = pick_by(ivs, key)
    print(f'  {name}: 选了 {len(got)} 个  {got}')
print('  枚举验出的最大值:', brute_max(ivs))

  按结束时间排: 选了 4 个  [(1, 4), (5, 7), (8, 11), (12, 14)]
  按开始时间排: 选了 3 个  [(0, 6), (6, 10), (12, 14)]
  按区间长度排: 选了 3 个  [(3, 5), (5, 7), (12, 14)]
  枚举验出的最大值: 4

按结束时间排拿到 4 个，正好是枚举出来的最大值；另外两种各差一个。

为什么是结束时间？因为按它排序时，每一步选的区间都给后面留下最大的余地——结束得越早，后面能接的越多。用交换论证说就是上面那三句话。

这一节的 lambda 你可能没见过，它是「没有名字的小函数」，lambda t: t[1] 等价于先写一个只返回 t[1] 的函数再传进来。第 5 课提过排序可以按关键字排，这里给的就是那个关键字。

排序关键字选错

按开始时间排「看着也行」，而且它在很多数据上真的不错。问题是它有时错。

给你一组它错得很惨的区间：一个从 0 到 100 的长区间，外加 6 个长度 1 的小区间。

bad = [(0, 100)] + [(2 * i + 1, 2 * i + 2) for i in range(6)]
for name, key in [('按结束时间排', lambda t: (t[1], t[0])),
                  ('按开始时间排', lambda t: (t[0], t[1]))]:
    got = pick_by(bad, key)
    print(f'  {name}: 选了 {len(got)} 个  {got}')
print('  枚举验出的最大值:', brute_max(bad))

  按结束时间排: 选了 6 个  [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12)]
  按开始时间排: 选了 1 个  [(0, 100)]
  枚举验出的最大值: 6

按开始时间排第一步就挑了那个从 0 开始的长区间，之后什么都接不上了——1 个，而最优是 6 个。

真正值得注意的是这个：

（本机实测，每组随机 300 次，每次都跟枚举出的真正最大值比。）

在「长度都差不多」的数据上，错误的策略一次都没错。 这就是它危险的地方——你拿小样例、拿随机数据试，试不出来；真到考场上碰上一长一短混在一起的数据（237/300 组），它立刻崩掉，而且崩得毫无征兆。

「有时对」在竞赛里等于「错」。 一道题只有一个答案要对。

贪心什么时候失效

回过头看找零那两套面额，能看出一条规律。

面额 1/5/10/25 里，每个面额都是前一个的整数倍左右，大面额永远能由小面额凑出来，而且不亏。所以挑最大的那枚永远不会让「剩下的金额」变成凑不出的形状。

面额 1/3/4 里，4 和 3 之间没有这种关系。凑 6 元的时候，挑 4 会留下 2——2 不是一个能高效凑出的形状（只能用两个 1）；而挑 3 留下 3，正好又是一枚。

所以判断贪心会不会失效，可以盯住这一句：当前这一步的选择，会不会把「剩下的问题」变成一个更难的形状？ 会，就得换方法。

几个常见的信号：

• 局部最优的选择限制了后面的选择（上面的长区间）。
• 需要在「多拿一点现在」和「留点余地给后面」之间权衡。
• 数据是混着来的：一部分很容易，一部分很极端。极端的那部分就是贪心的坟场。

失效了该换什么

贪心失效时，正确的做法不是给贪心打补丁，而是换方法。

最常见的换法是动态规划。上面那个 best_coins 就是：它不预设「该先拿哪个」，而是把金额 1、2、3、……、63 的最优枚数全部算出来，要算 6 的时候直接看 5、3、2 这三个已知的答案，挑最好的那个加一。

代价是慢一些（要开一张表，时间跟金额成正比），换来的是不用证明——递推关系写对，答案就是对的。

所以真正的选择顺序是：先想贪心，能写出交换论证就用贪心；写不出来，就别硬凑，直接上动态规划。 给失效的贪心打补丁（加几个特判、往回退一步重选）几乎总是错的——那等于用一堆不成体系的规则去模拟动态规划，还容易漏情况。

动态规划是下一课的内容。这一课只要记住：贪心失效不是「再改改」的信号，是「该换方法」的信号。

这一课用到的判断

• 贪心是「每一步选当前最好」，但它不保证全局最好：面额 1/5/10/25 时找零一枚不差，换成 1/3/4，凑 6 元贪心要 3 枚而最优只要 2 枚。
• 判断能不能贪，看「贪心选择性质」：每步选的那个当前最好，是否一定存在于某个全局最优解里。
• 证明性质的套路是交换论证：假设最优解与我不同 → 把第一个不同处换成我的选择，说明不会变坏也接得上 → 于是存在含我选择的最优解，归纳下去贪心解即最优解。写不出这三句话就别用贪心。
• 区间调度按结束时间排：结束得越早，给后面留的余地越大。实测拿到 4 个，与枚举的最大值一致。
• 按开始时间排是错的，但「有时才错」：区间长度都差不多时 0/300 组出错，一半短一半长时 210/300 组出错，最多差 5 个。「有时对」在竞赛里等于「错」，而它恰恰在小样例上试不出来。
• 也別按区间长度排：实测 297/300 组出错，比按开始时间排还糟。
• 贪心失效的信号：这一步的选择限制了后面的选择；需要在「现在多拿」和「以后有路」之间权衡；数据里混着极端情况。
• 失效了就换动态规划，别打补丁：动态规划要填表、慢一些，但不需要证明——递推写对，答案就对。

• 《算法导论（第 3 版）》第 16 章 贪心算法书 · 贪心选择性质、最优子结构、交换论证的完整写法
• OI Wiki · 贪心竞赛里常见的贪心模型与邻项交换法的证明模板
• 第 13 课：排序：分而治之的样板贪心常要排序，先排什么由策略决定
• 第 24 课：动态规划：把重复计算记下来贪心证不出来时该换的方法