贪心 (Greedy)

TL;DR

贪心不是"每一步选看起来最好的"，而是一种可证明的算法范式：如果问题有 最优子结构 + 无后效性，且每一步的局部最优决策"永远不会被未来的决策推翻"，那么局部最优的拼接就是全局最优。判断一个题能不能贪心，靠的不是直觉而是交换论证 / 归纳证明。本章给出判据、证明模板、四组经典问题的严格推导，以及 Go / Python 双语言实现。

读完应能：

1. 用"最优子结构 + 无后效性 + 贪心选择性质"三句话判断一个题能否贪心。
2. 用交换论证证明区间调度和 Huffman 的最优性。
3. 写出活动选择、部分背包、Huffman、任务调度的实现，并指出它们各自的"排序键"。
4. 说出贪心与 DP 的分界线：0/1 背包为什么不能贪心、部分背包为什么能。

一、思想链

工程问题: 每一步选当前最优, 能不能保证全局最优?
  └─► 必要条件1: 最优子结构 (子问题最优解能拼出全局最优)
  └─► 必要条件2: 无后效性 (未来决策只看当前状态)
  └─► 贪心选择性质: 存在一个"每一步都取局部最优"的最优解
        └─► 证明武器: 交换论证 / 归纳 / 拟阵(matroid)公理

二、形式化判据

设每一步要做的选择集合为 $C_i$，贪心选 $g_i \in C_i$：

1. 最优子结构：$OPT(S)$ 由 $g_1$ 与 $OPT(S_{g_1})$ 组合而成；
2. 无后效性（马尔可夫性）：$S_{g_1}$ 的选择与"怎么走到 $g_1$"无关；
3. 贪心选择性质：存在最优解以 $g_1$ 为第一步——证明方式是：任取一个最优解，把它"交换"成以 $g_1$ 开头且不劣。

三、经典问题与证明

3.1 活动选择（区间调度）

问题：$n$ 个区间 $[s_i, e_i)$，选最多互不重叠的区间。

贪心：按 end 升序排序，依次取不与已选重叠的最早结束区间。

交换论证：设贪心第一个区间是 $g_1=[s_{g}, e_{g}]$（全局最早结束），任意最优解 $O$ 的第一个区间是 $o_1=[s_o, e_o]$。因为 $e_g \le e_o$，把 $O$ 中的 $o_1$ 换成 $g_1$ 后，$O$ 的剩余区间仍然不重叠（它们都在 $e_o$ 之后开始，也在 $e_g$ 之后开始），所以存在以 $g_1$ 开头的最优解。对 $S_{g_1}$ 归纳即可。

3.2 部分背包（Fractional Knapsack）

贪心：按单位价值 $v_i/w_i$ 降序装，装不下时切碎。

为什么 0/1 背包不行：0/1 里"当前最值钱的物品"可能挤掉"组合后更优的两个物品"，后效性破坏；部分背包里一切可切，贪心选择性质成立（单位价值最高的物品在某个最优解里一定被完全或部分取走，交换论证）。

3.3 Huffman 编码

贪心：每次合并频率最小的两棵树（优先队列）。

最优性证明（交换论证两步）：

1. 频率最小的两个符号 $x,y$ 在某棵最优树里深度最深且互为兄弟（否则交换到最深不增加 WPL）；
2. 合并 $x,y$ 为新符号 $z$（$f_z=f_x+f_y$）后，原问题变成 $n-1$ 符号的子问题——由归纳，贪心持续最优。

3.4 SPT 调度

问题：单机、任务有处理时间 $p_i$，最小化平均完成时间。

贪心：按 $p_i$ 升序（Shortest Processing Time first）。

交换论证：若最优解中相邻两项 $p_a > p_b$（a 在 b 前），交换它们，只有这两项的完成时间变化：$p_a$ 延后 $p_b$、$p_b$ 提前 $p_a$，总完成时间减少 $p_a - p_b > 0$。所以最优解必按 $p_i$ 升序。

四、多语言实现

Go: 活动选择

type seg struct{ s, e int }

func maxActivities(a []seg) int {
    sort.Slice(a, func(i, j int) bool { return a[i].e < a[j].e })
    cnt, lastEnd := 0, -1
    for _, x := range a {
        if x.s >= lastEnd { // 不重叠
            cnt++
            lastEnd = x.e
        }
    }
    return cnt
}

Python: Huffman（证明等价的最小合并）

import heapq

def huffman_cost(freqs):
    heap = list(freqs)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a, b = heapq.heappop(heap), heapq.heappop(heap)
        total += a + b          # 每次合并的代价 = 树高累计
        heapq.heappush(heap, a + b)
    return total

五、工程里什么时候能用贪心

1. 输入有强结构（区间、单机队列、树、双值）——先试交换论证；
2. 能构造凸性：升级/定价问题里，代价函数凸时"最便宜优先"可证；
3. 没有结构就老实 DP / 回溯（见 dp.md 与 backtracking.md）。

六、易错清单

1. 排序键选错：区间调度按 end 而非 start/长度；任务调度按 p_i 而非截止期（截止期问题是 EDF，另一套判据）。
2. "看起来对"当证明：每个贪心必须配交换论证或反例自检——Huffman 看似显然，实际要两步交换证明。
3. 贪心 vs DP 分界：0/1 背包、带权区间调度（需 DP）、硬币找零（面额不整除时）都不能贪心。

七、一页速查

判据:   最优子结构 + 无后效性 + 贪心选择性质
证明:   交换论证(把最优解调成贪心解不劣) / 归纳 / 拟阵
模板:   选排序键 → 贪心选 → 交换论证验证
经典:   区间(按end) / 部分背包(按unit) / Huffman(最小堆) / SPT(按p)
分界:   可切分→贪心; 不可切分带后效→DP

下一篇: 动态规划 (DP)。