6.3 贪心算法：一步到位的取舍

6.3 贪心算法：一步到位的取舍

本节摘要：贪心算法每一步都做"当前看起来最好"的选择，且绝不反悔。它代码极短、效率极高，但正确性只在具备贪心选择性质的问题上成立——局部最优能拼出全局最优。本节用区间调度给出标准贪心与其证明思路（交换论证），用硬币找零的反例展示贪心失效现场，并给出"先证明再动手"的纪律。

每步都拿最大的，最后是赢是输

先看一个实验。硬币面额 1、3、4，要凑出 6：贪心策略"每次拿不超余额的最大面额"给出 4 + 1 + 1 共三枚；而最优解是 3 + 3 两枚。每一步都无可指摘（拿 4 时确实是最少枚数的直觉起点），合起来却输了——局部最优的堆叠不保证全局最优，这是贪心的第一课。

# 硬币找零：贪心的翻车现场
def greedy_coins(amount, coins):
    coins = sorted(coins, reverse=True)
    picked, rest = [], amount
    for c in coins:
        while rest >= c:
            picked.append(c)
            rest -= c
    return picked if rest == 0 else None

def best_coins(amount, coins):               # 动态规划兜底：求最少枚数
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if a >= c and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount]

amount, coins = 6, [1, 3, 4]
print("贪心解：", greedy_coins(amount, coins))
print("最优解：", best_coins(amount, coins), "枚")
# 输出：
# 贪心解： [4, 1, 1]
# 最优解： 2 枚
# 贪心三枚、最优两枚（3+3）——面额体系不配合，贪心当场翻车
​

同一套贪心在标准币制（1、5、10、50、100）上恰好正确——所以付零钱时收银员从不思考。贪心是否正确取决于问题结构，不取决于运气，判定手段就是下一小节的证明思路。先把结论放在这：贪心是五套范式里唯一"对了白赚、错了白干"的一套——代码十行以内，写错也是十行以内。

正确的贪心长什么样：区间调度

问题：会议室只能容纳一场活动，给出各活动的起止时间，最多能安排几场？贪心策略：按结束时间排序，每轮选结束最早且不与已选冲突的活动。

# 区间调度：按结束时间贪心，全程跟踪
def interval_schedule(intervals):
    picked = []
    end = float("-inf")
    for s, e in sorted(intervals, key=lambda x: x[1]):   # 关键：按结束时间排
        if s >= end:                    # 不与已选冲突
            picked.append((s, e))
            end = e
    return picked

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
plan = interval_schedule(acts)
print("入选活动：", plan)
print("共", len(plan), "场")
# 输出：
# 入选活动： [(1, 4), (5, 7), (8, 11), (12, 16)]
# 共 4 场
# 选 (1,4) 后排除所有 4 前开始的；选 (5,7) 再排除到 7；以此类推
​

为什么按结束时间排就正确？交换论证的思路：设最优解 O 的第一场不是结束最早的那场 A。把 O 的第一场换成 A——A 结束不晚于它，后续所有活动都不受影响（约束只会更松）。于是得到同样大小的另一个解。逐场替换下去，最优解可以完全变成贪心解，故贪心解就是最优。证明的支点是那句"换入的结束更早、约束更松"——它对"按开始时间""按时长排序"都不成立，这正是排序键选结束时间的原因。

硬币问题为什么证不动？因为"拿走一枚最大币"之后，剩余问题不再与原问题同构（最优解可能根本不含那枚 4），贪心选择性质不成立。判断顺序永远是：先找贪心策略，再问能否交换论证，最后才写代码。

贪心的正确打开方式

贪心家族里藏着一串老熟人，你早已在用：

• 第四章的 Dijkstra、Prim、Kruskal：每轮取"最近的未定型顶点 / 最便宜的横跨边"，都是贪心；非负权与切割定理分别是它们的正确性支柱；
• 哈夫曼编码：每轮合并频率最小的两个节点，构造最优前缀码（任何编码都不是另一编码的前缀——3.5 节 Trie 的词尾标记保证了可解码性）；
• 任务调度与截止时间：按截止时间排序的贪心是许多调度问题的最优解；
• 最小代价合并（石子合并的贪心版、哈夫曼同构）：每次合并最小两堆。

⚠️ 常见坑：把"贪心更快"当成"贪心更好"。贪心与动规的差别不是效率，是正确性边界：贪心错起来是答案本身错，而动规只是可能慢。没证明之前，贪心只能算猜想。

💡 关键直觉：能贪心的问题都有"越早决断越不吃亏"的单调结构——结束最早的活动占了不亏、最近的顶点定型不亏。找不到这种单调性，就老实填表。

走火入魔：无证明的贪心进生产

真实事故模板：任务权重不等时仍按截止时间贪心排产、图带负权仍用 Dijkstra、找零系统换了个面额组合没重新验证。共性都是把某个输入下的巧合当成了结构的必然。纪律：换币制、换权重、换约束，贪心的证明就要重做；动过问题的任何参数，先跑反例搜索（小规模暴力对拍，如上面 best_coins 的用法），再上线。

本节要点回顾

• 贪心 = 每步局部最优且不反悔；正确性需要贪心选择性质，靠交换论证确认；
• 硬币反例（面额 1、3、4 凑 6：贪心三枚对最优两枚）是"局部最优叠加失效"的最小样本；
• 区间调度按结束时间排序贪心可证最优：换入结束更早者只会放松约束，逐场替换后贪心解即最优解；
• 贪心老熟人：Dijkstra、Prim、Kruskal、哈夫曼——正确性各有支柱定理；
• 纪律：先证后写；参数一变重新验证；小规模与暴力对拍是贪心的体检手段。

当问题既不能贪心、也填不动表，只剩搜索一条路时，怎么走得又全又不傻——下一节回溯法。