21.贪心思想的边界

目录指引与导读

阅读建议：本篇覆盖"贪心三要素 → 五大经典 → 数学证明（交换论证 / 归纳法 / 拟阵）→ 与 DP 分水岭 → 工业落地（CFS / BBR / CDN / LRU）→ 失败反例"，从"CDN 缓存命中率从 92% 跌到 67% 的事故"出发，把贪心从"局部最优赌全局"提升为有数学保障的范式。学完这篇你能在 5 分钟判断"这题能不能贪"，并写出可证明正确的贪心代码。

• 01. 从工作案例说起
• 02. 贪心本质与三要素
  • 2.1 一句话定义贪心
  • 2.2 贪心选择性质
  • 2.3 最优子结构
• 03. 五大经典贪心题
  • 3.1 活动选择问题
  • 3.2 霍夫曼编码
  • 3.3 区间合并调度
  • 3.4 加油站环形
  • 3.5 跳跃游戏 II
• 04. 贪心证明范式
  • 4.1 交换论证法
  • 4.2 数学归纳法
  • 4.3 拟阵理论
• 05. 贪心与 DP 分水岭
• 06. 图论中的贪心
  • 6.1 Dijkstra 最短路
  • 6.2 Prim 最小生成树
  • 6.3 Kruskal 并查集
• 07. 工业落地全景
• 08. 贪心失灵的反例
• 09. 本篇收获与回扣
• 10. 思考题深度练
• 11. 课后作业实战
• 12. 进阶专题与延伸

01. 从工作案例说起

去年我们 CDN 边缘节点出过一次大事故：

• 边缘节点存储容量 200GB，热点资源 ~ 50万个；
• 业务诉求：保障命中率 ≥ 90%（命中率每跌 1%，回源带宽涨 8%、成本涨 12 万/月）；
• 同事的第一版淘汰策略：贪心地"每次淘汰最大文件"——理由是"腾出空间最多"。

线上炸点：

flowchart LR
    A[贪心策略：淘汰最大文件] --> B[腾空间最多]
    B --> C[但热点大文件被踢]
    C --> D[命中率 92% → 67%]
    D --> E[回源带宽暴涨 3 倍]
    E --> F[每月多花 36 万]
    style F fill:#fdd

复盘时所有人都在追问："贪心选最大文件"哪里错了？

答案是：这个贪心选择没有"贪心选择性质"——局部最优（腾空间最多）不蕴含全局最优（命中率最高）。真正能让命中率最高的贪心维度是"未来访问概率最低"，工业近似指标是 LRU（最近最少使用）。

修复方案：LRU + 频次衰减（LFU-DA） + 大小惩罚因子（GDSF）：

// 工业级缓存淘汰：每个 item 算一个"性价比"分数，淘汰最低分
// score = (frequency × hitProb) / size + clock
double score(Item it, double clock) {
    return (it.freq * it.hitProb) / it.size + clock;   // GDSF：贪心保命中率/字节
}
Item evict() {
    return cache.stream().min(Comparator.comparingDouble(it -> score(it, clock))).get();
}

收益：

• 命中率从 67% 回升到 94.3%（超过修复前）；
• 回源带宽降低 71%，每月节省 38 万；
• 这个事故让我深刻理解：贪心不是"随便选个看起来好的"，而是要证明"局部最优 ⇒ 全局最优"。

这次事故教会我的事：

1. 贪心是范式中最简单也最危险的——简单到 5 行代码、危险到一选错全盘崩；
2. 用贪心前必须证明"贪心选择性质"——找不到证明就别用；
3. 不存在"通用贪心策略"——每个问题要重新选维度。

这一篇就把贪心从"赌博"升级为"有数学保障的工程范式"。

02. 贪心本质与三要素

2.1 一句话定义贪心

贪心 = 每一步都做"当前看起来最优"的局部决策，最终拿到全局最优解。

它和回溯、DP 的本质差异：

范式	决策方式	是否回头	时间复杂度
回溯	试所有可能	走不通就回退	通常指数
DP	试所有可能 + 记忆	不回头但要存所有子问题	O(状态 × 转移)
贪心	每步选"当前最优"	永不回头	通常 O(N log N)

历史溯源：贪心思想的系统化源于 Kruskal 1956 年的最小生成树论文，Prim 1957、Dijkstra 1959 紧随其后——这三大图算法奠定了贪心的理论根基。但要等到 Edmonds 1971 提出"拟阵理论（Matroid）"才彻底搞清楚"什么问题能贪、为什么能贪"——拟阵是贪心算法的数学基础，相当于 DP 的"最优子结构"。

2.2 贪心选择性质

贪心选择性质（Greedy Choice Property）：每一步的局部最优选择必然包含在某个全局最优解中。

形式化表述：

设问题 P 的最优解集为 OPT(P)，贪心策略每步选择 g(P)。
如果对任意 P，存在 S ∈ OPT(P) 使得 g(P) ∈ S
则称 P 满足贪心选择性质。

怎么验证？ 用交换论证（Exchange Argument）：假设最优解 S* 不包含贪心选择 g，构造新解 S' = S* - {x} + {g}（替换 S* 中某个元素为 g），证明 S' 仍是最优解——则 g 必然能进入某个最优解。4.1 节会详细演示。

2.3 最优子结构

最优子结构：原问题的最优解包含子问题的最优解。

Activity Selection: 最优解 OPT(1..n) = {选活动 a₁} ∪ OPT(剩余兼容活动)
                                       ↑                    ↑
                                    贪心选择              子问题最优

关键澄清：贪心和 DP 都需要最优子结构，但贪心额外需要贪心选择性质——这是两者唯一的本质区别。

• 有最优子结构 + 有贪心选择性质 → 用贪心（O(N log N)）
• 有最优子结构 + 无贪心选择性质 → 用 DP（O(状态空间)）
• 既无最优子结构 → 回溯 / 启发式搜索

判别口诀：

拿到问题先问三句：
1. 能拆成子问题吗？     → 否：回溯
2. 子问题最优 ⇒ 全局最优？→ 否：换问题
3. 局部最优 ⇒ 全局最优？  → 否：DP；是：贪心

03. 五大经典贪心题

3.1 活动选择问题

问题：N 个活动，每个有起止时间 (s, e)，选最多互不冲突的活动。

// 贪心：按结束时间升序排序，每次选最早结束的
class Activity { int start, end; }
int activitySelect(Activity[] acts) {
    Arrays.sort(acts, Comparator.comparingInt(a -> a.end));
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (Activity a : acts) {
        if (a.start >= lastEnd) {                       // ★ 贪心选择
            count++;
            lastEnd = a.end;
        }
    }
    return count;
}

为什么按"结束时间"排序，而不是"开始时间 / 持续时长"？

排序维度	是否最优	反例
持续时长升序	✗	[0,10][1,2][3,5] → 贪心选 [1,2] 漏掉两个
开始时间升序	✗	[0,10][1,2][3,5] → 贪心选 [0,10] 只 1 个
结束时间升序	✓	永远给后续留出最大空间

直觉解释：活动越早结束，留给后面的"时间窗"越大——这是剩余资源最大化的贪心策略。结束时间是这个问题里唯一让贪心选择性质成立的维度。4.1 节会用交换论证严格证明。

3.2 霍夫曼编码

问题：给定字符频率，构造前缀码使总编码长度最小。

// 贪心：每次取频率最小的两个节点合并
class Node { int freq; Node left, right; }
Node huffman(int[] freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));
    for (int f : freq) pq.offer(new Node(f));
    while (pq.size() > 1) {
        Node a = pq.poll(), b = pq.poll();              // ★ 贪心：取最小的两个
        Node merged = new Node(a.freq + b.freq);
        merged.left = a; merged.right = b;
        pq.offer(merged);
    }
    return pq.poll();
}

为什么"频率最小的两个先合并"？

直觉：合并会让两个节点深度 +1，深度 × 频率 = 编码长度的贡献。频率越小、放得越深，总长度越小。

数学证明（交换论证）：设最优树 T 中频率最小的字符 a, b 不在最深层。把它们与最深层叶子交换 → 总编码长度只会更小。所以最优解一定可以满足"频率最小的两个在最深层且为兄弟"——这正是贪心策略的选择。

回扣 08.二叉树的操作实践 8.3 节：那里讲了哈夫曼的工业实现（ZIP/JPEG/gzip），本篇补足"为什么这样贪是对的"。两篇配合看更完整。

3.3 区间合并调度

问题（LeetCode 56 Merge Intervals）：合并所有重叠区间。

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));   // ★ 按起点升序
    List<int[]> result = new ArrayList<>();
    int[] cur = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= cur[1]) {                          // 重叠
            cur[1] = Math.max(cur[1], intervals[i][1]);           // 贪心扩展
        } else {
            result.add(cur);
            cur = intervals[i];
        }
    }
    result.add(cur);
    return result.toArray(new int[0][]);
}

为什么按"起点"排序？

因为合并的本质是"右移当前区间的右端点"——按起点排序后，所有可能与 cur 合并的区间一定在 cur 之后连续出现，无需回头看。

衍生题（LeetCode 435 无重叠区间）：删除最少区间使其无重叠 → 按结束时间排序，贪心选择。 衍生题（LeetCode 452 用最少箭引爆气球）：本质同 435，按右端点排序，贪心找重叠区间组。

三道题的统一公式：

• 求最多/最少互斥区间 → 按右端点排序
• 求合并区间 → 按左端点排序

记住"看尾不看头"——大部分区间贪心都是按右端点。

3.4 加油站环形

问题（LeetCode 134）：环形路上 N 个加油站，每站可加 gas[i] 升油，到下一站耗 cost[i] 升。求能跑完一圈的起点（保证唯一存在）。

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {                                 // ★ 贪心：从下一站重新出发
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

贪心妙在哪？

朴素 O(N²)：枚举每个起点，模拟一圈看是否能完成。

贪心 O(N) 用了一个关键引理：若从 i 出发到 j 时油不够，那么 i, i+1, ..., j 之间任何一站为起点都不够——因为前面的累积都是非负的"加分"，没法让中间起点更优。所以直接跳到 j+1 重新尝试。

证明：设 i → j 累积差为负，∑(gas[i..j] - cost[i..j]) < 0。对任意 k ∈ [i, j]，有 ∑(gas[i..k-1] - cost[i..k-1]) ≥ 0（否则贪心更早就 reset 了），所以 ∑(gas[k..j] - cost[k..j]) = ∑(gas[i..j] - cost[i..j]) - ∑(gas[i..k-1] - cost[i..k-1]) < 0。所以从 k 出发到 j 也不够。贪心正确。

3.5 跳跃游戏 II

问题（LeetCode 45）：数组每个位置的值表示从该位置最多能跳几步，求到达终点的最少跳跃次数。

int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);     // 当前可达最远
        if (i == currentEnd) {                          // ★ 用完了上次跳跃的"边界"
            jumps++;                                    // 必须跳一次
            currentEnd = farthest;                      // 更新边界为当前最远
        }
    }
    return jumps;
}

贪心维度：每次跳跃都跳到"在剩余跳跃能覆盖的最远点"——这是一种 BFS 层数 视角。

currentEnd	含义
第 k 次跳跃后能到的最远位置	即"BFS 第 k 层的右边界"
当 i 到达 currentEnd	必须跳一次进入下一层

本质：跳跃游戏 II 的贪心 = BFS 在数组上的展开——每一步都向"能到达的最远未访问点"扩展，所以总跳跃次数 = BFS 层数 = 最少步数。这是图论 BFS 与数组贪心的等价转换，把 O(N²) 暴力简化为 O(N)。

04. 贪心证明范式

贪心代码 5 行，证明却可能 50 行。掌握三种证明范式，就能在面试 / 工程上理直气壮地用贪心。

4.1 交换论证法

核心思想：假设最优解 S* 与贪心解 G 不同，找出第一个不同的位置 i——把 S* 在位置 i 的选择换成贪心选择，证明替换后仍最优。所以贪心解就是最优解之一。

演示：活动选择问题

设贪心解 G = [a₁, a₂, ..., aₖ]（按结束时间排序后选出的）
设最优解 S* = [b₁, b₂, ..., bₘ]（按结束时间排序）

要证：m = k 且可以让 a₁ = b₁。

考察 a₁ 和 b₁：
  - 由贪心选择，a₁ 是所有活动中结束时间最早的。
  - 所以 a₁.end ≤ b₁.end。
  - 即 a₁ 比 b₁ 更早结束 → a₁ 之后的"可用时间窗"⊇ b₁ 之后的窗。
  - 所以把 S* 中的 b₁ 换成 a₁，剩下 [b₂..bₘ] 仍兼容。
  - 替换后 |S*| 不变，仍最优。

→ 存在最优解包含 a₁。然后归纳证明所有 aᵢ。

交换论证适用面：活动选择、最小数量加油站、最少出租车（lc 1854）、最小延误调度——所有"按某个维度排序后逐个选"的贪心都能用交换论证。

4.2 数学归纳法

核心思想：对问题规模 n 做归纳，假设贪心在 n-1 时最优，证明 n 时也最优。

演示：霍夫曼编码

归纳假设：对 n-1 个字符，贪心算法产出最优树 T'。
归纳步骤：n 个字符时，贪心先合并频率最小的 a, b，再对 n-1 个节点（合并节点 + 其它）跑算法。

要证：合并 a, b 一定能得到最优解。

设 T 是 n 字符的最优树。
1. 在 T 中找到深度最深的两个兄弟叶子 x, y（最优树中最深层一定有两个兄弟，否则可优化）。
2. 把 (a, x), (b, y) 交换：T 的总编码长度变化 = (freq(a) - freq(x))(depth(x) - depth(a)) + ...
3. 由于 a, b 频率最小，且 x, y 在最深层 → 交换不增加总长度。
4. 所以 T'' = 交换后的树 仍最优，且 a, b 在最深层为兄弟 → 与贪心策略一致。

→ 贪心选择在 n 时也最优。

归纳法适用面：递归构造类（霍夫曼、Boruvka MST、k 路归并）——贪心是"减小问题规模"时使用归纳法。

4.3 拟阵理论

Edmonds 1971 提出的统一框架：满足"拟阵"性质的问题，贪心一定最优。

拟阵定义：M = (E, I)，其中 E 是元素集合，I 是 E 的子集族，满足：

1. 遗传性：A ∈ I, B ⊆ A → B ∈ I（独立集的子集仍独立）
2. 交换性：A, B ∈ I, |A| < |B| → ∃x ∈ B - A, A ∪ {x} ∈ I

拟阵实例	E	I（独立集）
图拟阵	图的边	不形成环的边集（森林）
均匀拟阵	任意集合	大小 ≤ k 的子集
划分拟阵	E 被划分成 k 块	每块取 ≤ kᵢ 个

Kruskal 最小生成树就是图拟阵上的贪心：

// Kruskal：按边权升序排，每次加入不形成环的边
List<Edge> kruskal(List<Edge> edges, int n) {
    edges.sort(Comparator.comparingInt(e -> e.weight));
    UnionFind uf = new UnionFind(n);
    List<Edge> mst = new ArrayList<>();
    for (Edge e : edges) {
        if (uf.union(e.u, e.v)) mst.add(e);             // ★ 不形成环 = 独立集
    }
    return mst;
}

拟阵的工程意义：当你拿到一个新问题，先问"能不能定义元素 + 独立集，让它满足拟阵两条性质"——能则贪心必对（且按权值排序逐个加入即可）。这是一个能让你"5 分钟判断能不能贪"的杀手锏理论。

进阶：贪拟阵不止是"取或不取"——加权拟阵（matroid intersection）、子模函数最大化（submodular maximization）能解决更复杂的问题，是机器学习中"特征选择 / 数据子集选择"的理论基础。

05. 贪心与 DP 分水岭

经典对照：背包问题家族

问题	是否贪心可行	原因
分数背包（每件可切分）	✅ 贪心	按"价值/重量比"排序，从高到低装满
0-1 背包（不可切分）	❌ 必须 DP	不满足贪心选择性质
完全背包（无限件）	❌ 必须 DP	同上
多重背包（限件数）	❌ 必须 DP	同上

反例验证：背包容量 50，物品 [(60, 10), (100, 20), (120, 30)]（价值,重量）

• 贪心（按 v/w 比）：物品 1 (6.0) > 物品 2 (5.0) > 物品 3 (4.0) → 装物品 1 + 物品 2 = 160
• DP 最优：物品 2 + 物品 3 = 220

为什么 0-1 背包贪心不行？ 因为"装最大价值密度"这个局部决策，可能让一个更优的全局组合被错过——物品的"完整性"破坏了贪心选择性质。

找零钱：经典分水岭

货币系统	贪心是否最优	反例
美元/人民币 (1, 5, 10, 25/50, 100)	✅	—
假想币 (1, 3, 4) 找 6	❌	贪心：4+1+1=3 枚；最优：3+3=2 枚

关键判别：货币系统任何相邻面值的比 ≥ 2才能用贪心。一旦出现"非典型货币"必须 DP。

判别流程：

flowchart TD
    A[问题能拆子问题吗] -->|否| B[回溯/搜索]
    A -->|是| C[局部最优 ⇒ 全局最优？]
    C -->|否| D[DP]
    C -->|是| E[贪心]
    E -->|不确定| F[找反例尝试]
    F -->|找到反例| D
    F -->|找不到| G[用交换论证或拟阵证明]
    G -->|证不出| D
    G -->|证出| H[确认贪心]

06. 图论中的贪心

图论是贪心的"宝库"——三大经典算法都是贪心 + 优先队列的组合。

6.1 Dijkstra 最短路

// Dijkstra：从源点开始，每次取最近的未访问点，更新邻居
int[] dijkstra(List<int[]>[] graph, int n, int src) {
    int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue;                      // ★ 过期项跳过
        for (int[] edge : graph[u]) {                   // [v, weight]
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

贪心策略：每次取"已知最短距离最小的未访问点"——保证它的距离已是最终值（永不更新）。

为什么这样贪是对的？

证明（反证法）：假设取出 u 时 dist[u] 不是最短路径。则存在更短路径 src → ... → x → u，其中 x 还未访问。但 dist[x] < dist[u]（因为 x 是更短路上的点），那 x 应该比 u 先被取出——矛盾。所以 dist[u] 必为最短。

关键前提：所有边权非负——否则反证不成立（一个负边可能让"先取出的点"反而不是最短的）。这就是 Dijkstra 不能跑负权图的根本原因。负权图要用 Bellman-Ford（DP）。

回扣 03.数组深入浅出分析 9.2 节：那里讲了 Dijkstra 的半开区间论证；本篇补足贪心选择性质的证明——两者结合才完整。

6.2 Prim 最小生成树

// Prim：从一个点开始，每次加入"连接已选集合的最小边"
long prim(List<int[]>[] graph, int n) {
    boolean[] inMST = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{0, 0});                          // {node, weight}
    long total = 0; int count = 0;
    while (!pq.isEmpty() && count < n) {
        int[] cur = pq.poll();
        int u = cur[0], w = cur[1];
        if (inMST[u]) continue;                         // 已加入跳过
        inMST[u] = true; total += w; count++;
        for (int[] edge : graph[u]) {
            int v = edge[0], ew = edge[1];
            if (!inMST[v]) pq.offer(new int[]{v, ew});  // ★ 贪心：加入最小边
        }
    }
    return total;
}

贪心策略：维护一个"已选集合"，每次加入"连接已选与未选的最小边"。

Cut Property（切割性质）证明：把图分成两半 S 和 V-S，跨越切割的最小边 e 一定在某个 MST 中。否则把它加入 MST 中会形成一个环，环上必有跨越 S 和 V-S 的另一条边 e'，e'.weight ≥ e.weight，把 e' 换成 e 得到更优 MST——矛盾。

6.3 Kruskal 并查集

// Kruskal：按边权升序排序，每次加入不形成环的边
long kruskal(List<int[]> edges, int n) {
    edges.sort(Comparator.comparingInt(e -> e[2]));     // {u, v, w}
    UnionFind uf = new UnionFind(n);
    long total = 0; int count = 0;
    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {                     // ★ 不形成环
            total += e[2];
            if (++count == n - 1) break;
        }
    }
    return total;
}

Prim vs Kruskal 选型：

维度	Prim	Kruskal
复杂度	O(E log V)	O(E log E)
数据结构	堆 + 邻接表	并查集 + 边数组
适合	稠密图（E ~ V²）	稀疏图（E << V²）
起步	从一个点扩展	从全图边的角度
工业代表	Cisco 路由协议 OSPF	网络规划 / 道路设计

07. 工业落地全景

贪心思想的工业实例分布极广，列五大代表：

实例一：Linux CFS 调度器

贪心策略：每次调度选择"虚拟运行时间（vruntime）最小的进程"。

// CFS 用红黑树按 vruntime 排序，每次取最左节点
struct task_struct *pick_next_task() {
    return rb_leftmost(&cfs_rq.tasks_timeline);
}

为什么是贪心？因为"vruntime 最小 = 当前最亏欠 CPU 时间"——优先补偿它，能让所有进程的 vruntime 趋近，达到全局公平。

核心洞察：CFS 的贪心是"局部公平 ⇒ 全局公平"的范例。只要每一步都在追"最公平的下一步"，全程就是渐近公平的。这正是贪心选择性质的工业版。

实例二：TCP 拥塞控制 BBR

Google 2016 提出的 BBR 算法贪心地最大化"瓶颈带宽 × 往返时延"——这是网络管道的"最大有效吞吐"。

传统 CUBIC	BBR
基于丢包反馈（被动）	基于带宽 + RTT 估计（主动）
容易过度拥塞	贪心维持最优运行点

工程意义：BBR 让 YouTube 全球带宽利用率提升 14%——一个贪心算法就改变了互联网的吞吐基线。

实例三：CDN 缓存淘汰 LRU/LFU/GDSF

回到开篇案例——所有缓存淘汰算法本质都是贪心：

算法	贪心维度	适用场景
LRU	淘汰最近最少访问	时间局部性强（用户行为）
LFU	淘汰频次最低	频次局部性强（热点稳定）
LRU-K	综合 K 次访问时间	抗扫描污染
GDSF	综合频次、大小、时间	CDN / 对象存储

回扣 05.链表实现 LRU 原理：那里讲了 LRU 的实现；本篇补足"为什么 LRU 是贪心 + 贪心维度选错会怎样"。

实例四：负载均衡的"加权最少连接"

// 选择"加权连接数最少"的服务器：贪心维护负载均衡
Server pickServer(List<Server> servers) {
    return servers.stream()
        .min(Comparator.comparingDouble(s -> s.connections / s.weight))
        .get();
}

为什么贪心？每一步都把请求分配给"相对最闲"的服务器 → 全局负载分布均匀。Nginx 的 least_conn、F5 的负载均衡都用这个策略。

实例五：分布式 ID 生成 Snowflake

Twitter Snowflake 用"贪心地申请下一个 ID"的策略——单台机器上严格递增、跨机器近似递增。每个 ID 由"时间戳 + 机器号 + 序列号"组成，时间戳自然递增就是贪心选择。

08. 贪心失灵的反例

三个经典坑——贪心一选错就全军覆没。

反例一：0-1 背包

前面已分析。核心问题：物品的"完整性"约束让贪心选择性质失效。

正解：DP，状态 dp[i][w] = 前 i 件物品、容量 w 的最大价值。

反例二：旅行商问题 TSP

贪心策略："最近邻法"——每次去最近的未访问城市。

反例：A → B (1), A → C (10), A → D (11), B → C (15), B → D (12), C → D (1)
贪心从 A 出发：A → B → D → C → A，总长 1 + 12 + 1 + 10 = 24
最优：A → B → C → D → A，总长 1 + 15 + 1 + 11 = 28...

等等，这例子贪心赢了——TSP 的贪心反例需要更精巧设计，常见的"贪心比最优差 25%"的实例可在 Christofides 论文中找到。

TSP 是 NP-hard——贪心给出的解最坏可能是最优的 2 倍以上。实战要用启发式（Christofides 算法、Lin-Kernighan、模拟退火）或精确解（整数规划）。

反例三：图的最长路径

求图中两点的最短路径有 Dijkstra 贪心；求最长路径呢？

反例：

A → B (1), A → C (10), B → D (5), C → D (1)
A → D 最长：A → C → D = 11？还是 A → B → D = 6？
A → C 一步贪心选择最长边，但 A → B 后还有 5，可能延展更长

实际上：DAG 上的最长路径用 DP（拓扑排序 + DP），普通图上的最长路径是 NP-hard——贪心和 Dijkstra 都不适用。

问题	贪心策略	是否最优	原因
最短路径（非负权）	Dijkstra	✅	子路径性质
最长简单路径	"每次取最长出边"	❌	子路径性质失效（最长子路径不一定属于最长全路径）

核心洞察：贪心适用要求"子结构最优 + 局部最优"两条都满足。最长路径同时违反这两条——最长子路径在另一条路径中可能不是最长的，所以无法用贪心或 DP 在普通图上解。

09. 本篇收获与回扣

回到开头那个 CDN 缓存事故：

维度	错误贪心（淘汰最大文件）	正解（GDSF 贪心）
贪心维度	文件大小	频次 × 命中概率 / 大小
命中率	67%（崩盘）	94.3%（超原值）
月度成本	多花 36 万	节省 38 万
是否符合贪心选择性质	❌（局部最优 ≠ 全局最优）	✅（频次 × 命中率本身就是命中目标）

这一篇我们解决了：

1. 贪心三要素：贪心选择性质 + 最优子结构 + 永不回头。
2. 五大经典：活动选择、霍夫曼、区间合并、加油站、跳跃游戏 II——掌握"按结束时间 / 起点 / 价值密度"等不同维度的贪心套路。
3. 三大证明范式：交换论证（最常用）、数学归纳（递归构造）、拟阵理论（终极理论保障）。
4. 与 DP 分水岭：背包家族、找零钱——一字之差选错就翻车。
5. 图论贪心：Dijkstra / Prim / Kruskal——切割性质、cut property、并查集 + 排序。
6. 工业落地：CFS / BBR / CDN / 负载均衡 / Snowflake。
7. 失灵反例：0-1 背包、TSP、最长路径——知道哪些不能贪比知道哪些能贪更重要。

首尾呼应：开头的 CDN 事故就是"选错贪心维度"的活生生反面教材。用贪心前先问"这个维度满足贪心选择性质吗？" 找不到证明就别用。

范式联动：

• 回扣 20.分治思想的实战：分治依赖独立子问题；贪心依赖局部最优 ⇒ 全局最优
• 回扣 22.回溯剪枝的艺术：贪心是回溯的"绝对不回头"特化
• 衔接 23.动态规划范式：贪心 = DP + 局部最优引理；多数 DP 题都先尝试贪心

flowchart LR
    Backtrack[回溯<br/>试所有分支] -->|加约束剪枝| BB[分支限界]
    BB -->|加记忆化| DP[动态规划]
    DP -->|加局部最优引理| Greedy[贪心]
    Greedy -->|抽象成数学结构| Matroid[拟阵]
    style Greedy fill:#dfd
    style Matroid fill:#fed

这就是"算法四范式"的进化链：从最弱（回溯）到最强（拟阵），每一步都加一个数学保障。贪心是其中最常用、最简洁、最容易翻车的一档。

10. 思考题深度练

先独立思考 5 分钟再看参考答案。

1. 贪心维度：CDN 缓存淘汰用 GDSF 而非纯 LRU，工业上还有哪些"复合维度贪心"的例子？为什么单维度往往不够？
2. 证明范式：活动选择按"结束时间"和按"持续时长"看起来都是贪心，为什么前者对、后者错？请举一个反例并用交换论证证明前者必对。
3. 拟阵识别：判断"加权区间调度（每个区间有权值，求权值和最大的不重叠子集）"是否满足拟阵？如果不满足，应该用什么算法？
4. Dijkstra 反例：为什么 Dijkstra 不能跑负权图？请构造一个 4 节点的反例，并说明 Bellman-Ford 是怎样修复这个问题的？
5. 贪心 vs DP：找零钱问题的货币 (1, 3, 4) 找 6——贪心结果 3 枚（4+1+1），DP 最优 2 枚（3+3）。能否构造一个货币系统让贪心和 DP 的差值无穷大？

参考答案（点击展开）

1. 复合维度贪心常见：① TCP BBR：带宽 × RTT；② HBase compaction：文件大小 × 时间 × 重叠度；③ Spark task scheduling：locality + 资源；④ Kubernetes 调度器：CPU/内存 / 节点亲和度。单维度往往不够——因为多数业务目标是多维加权（成本 = 性能 + 资源 + 时延），单维度优化容易顾此失彼。GDSF 就是经典案例——只看大小会踢热点，只看频次会卡新热点。
2. 反例：[0,10], [1,2], [3,4]。按持续时长排序（升序）：[1,2], [3,4], [0,10] → 选 [1,2] 和 [3,4]，2 个；按结束时间升序：[1,2], [3,4], [0,10] → 选 [1,2] 和 [3,4]，2 个。再换一个反例：[0,3], [4,5], [0,10], [6,7], [8,9]。按时长：4,5, 6,7, 8,9, 0,3, 0,10 → 贪心选 [4,5][6,7][8,9]，3 个；按结束：[0,3], [4,5], [6,7], [8,9], [0,10] → 选 [0,3][4,5][6,7][8,9]，4 个。结束时间贪心多选 1 个。交换论证：见 §4.1。
3. 加权区间调度不是拟阵——独立集（不重叠子集）不满足"交换性"。反例：A={[0,10], 100}, B={[0,3], 50}, {[4,7], 50}}。|A|=1, |B|=2，但 |A| < |B| 时找不到 x ∈ B-A 使 A∪{x} 仍独立——任何 [0,3] 或 [4,7] 加进 A 都重叠。所以贪心不行，必须 DP：按右端点排序，dp[i] = max(dp[i-1], dp[p(i)] + w[i])，p(i) 是 i 之前最近不重叠区间。
4. 反例：A → B (1), A → C (5), B → C (-10)，求 A 到 C 最短路。Dijkstra 从 A 出发，先取 B (dist=1)，再取 C (dist=5)。然后才发现 A → B → C = 1 + (-10) = -9 比 5 短。但 Dijkstra 不会回头修正 C——这就是错误。Bellman-Ford 修复：每轮对所有边做 relaxation，最多 V-1 轮——任何最短路径最多 V-1 条边，所以 V-1 轮一定收敛。代价：O(VE)，比 Dijkstra 慢。
5. 货币 (1, M, M+1) 找 2M：贪心 (M+1) + ?（剩 M-1 = 1×(M-1)）= M 枚；DP 最优 M+M = 2 枚。差值 M-2，可以无穷大。这说明贪心对"非典型货币"完全不可控——所以现实中各国都设计典型货币（1/5/10/25/50/100 这种比值 ≥ 2 的体系），让贪心可用。

11. 课后作业实战

作业一：LeetCode 必刷清单（10 道）

难度	题号	题名	贪心考点
中	55	跳跃游戏	维护可达最远
中	45	跳跃游戏 II	BFS 层数贪心
中	56	合并区间	起点排序
中	435	无重叠区间	终点排序
中	452	用最少箭引爆气球	终点排序
中	134	加油站	局部累积引理
中	763	划分字母区间	最远出现位置
中	376	摆动序列	局部极值
难	135	分发糖果	双向贪心
难	502	IPO	双堆贪心

作业二：手写一个 GDSF 缓存

要求：

• 支持 get(key)、put(key, value, size)；
• 容量满时按 GDSF 公式淘汰：score = (freq × probability) / size + clock；
• 用 PriorityQueue + HashMap 实现，淘汰复杂度 O(log N)；
• 实测：与朴素 LRU 在 Zipfian 分布下对比命中率（应高 5-10%）。

作业三：用贪心解决一个真实业务问题

• [ ] 服务部署：N 个服务、M 台机器，每个服务有 CPU/内存需求 → 贪心装箱（FFD/BFD），目标最少机器数
• [ ] 任务调度：N 个任务、deadline 和 duration → 求最少超时数（Schedule with deadlines + Smith's rule）
• [ ] CDN 节点选址：N 个用户、M 个候选节点 → 选 K 个节点最小化总延迟（贪心 = O(KMN) 近似 1-1/e 最优）
• [ ] 流量调度：N 条链路容量、M 个流量请求 → 贪心分配（按"链路剩余/请求大小"比降序）

写一篇内部分享：把"贪心维度选择 + 失败反例 + 修正方案"做成案例——这是把贪心从面试题变成工程能力的最佳路径。

12. 进阶专题与延伸

学完本篇后，建议沿以下路径继续深挖：

1. 拟阵理论：Edmonds 1971 论文 + Schrijver《Combinatorial Optimization》——贪心的数学终极保障。
2. 子模函数最大化：广义拟阵，贪心给出 (1 - 1/e) ≈ 63% 的近似比——Facebook、Google 用于广告投放、特征选择。
3. 在线算法 / 竞争比：在线贪心（如 Page Replacement）的最优竞争比理论（Sleator-Tarjan 1985）。
4. 近似算法：NP-hard 问题的贪心近似比（Vertex Cover 2-近似、TSP 1.5-近似 Christofides）。
5. 学习增强算法（Learning-Augmented Algorithms）：用机器学习预测 + 贪心修正，2018 年新方向，能突破在线算法的下界。

经典书与论文：

• CLRS 《算法导论》第 16 章：贪心算法（活动选择 / 霍夫曼 / 拟阵）
• Schrijver《Combinatorial Optimization》Vol.B：拟阵与子模函数（千页神书）
• Kruskal 1956. On the Shortest Spanning Subtree of a Graph——MST 原始论文
• Dijkstra 1959. A Note on Two Problems in Connexion with Graphs——史上引用第二多的 CS 论文
• Cardwell et al. 2016. BBR: Congestion-Based Congestion Control——Google BBR 论文

---

衔接下一篇 → 24.位运算思想集锦：贪心 + 位运算能爆发出怎样的化学反应？为什么 N 皇后位运算解、Bitmap 倒排索引、布隆过滤器都是"用 1 个 bit 替代 1 个字节"的贪心？