Greedy

贪心在做什么

贪心(Greedy):每一步都做当前看起来最优的选择,不回头。

贪心:   局部最优 → 局部最优 → ... → 全局最优(?)
DP:     枚举所有选择,取全局最优

核心难点:贪心不一定对。它的正确性必须证明,不能靠"感觉"和"样例过了"。

什么时候贪心是对的

需要两个性质:

  1. 贪心选择性质(Greedy Choice Property):可以从局部最优选择出发构造出全局最优解。即:第一个选择可以贪心地做,而不用考虑它对后续的影响。
  2. 最优子结构(Optimal Substructure):做出贪心选择后,剩余的子问题与原问题同构,且原问题的最优解包含子问题的最优解。

对比 DP:DP 也有最优子结构,但没有贪心选择性质——DP 需要枚举第一个选择,贪心直接选定。

怎么证明 / 证伪

证伪:找反例

先尝试构造反例,比证明快得多。经典的反例套路:

  • 贪心的选择导致后续没有可行的搭配
  • 贪心的选择占用了稀缺资源,后面的选择更需要它

例:0-1 背包不能用"性价比最高优先"贪心:

容量 10
物品 A: 重 6, 值 30   (性价比 5)
物品 B: 重 5, 值 24   (性价比 4.8)
物品 C: 重 5, 值 24

按性价比贪心: 选 A (30), 剩 4 装不下 → 总价值 30
最优解:       选 B + C → 总价值 48

A 的性价比最高,但它占用了容量,导致后面两个都装不下。

证明方法

1. 交换论证(Exchange Argument)

最常用。思路:

1. 取任意最优解 OPT
2. 逐步把 OPT 里的选择"交换"成贪心的选择
3. 证明每步交换后仍然是最优解(或不更差)
4. 最终 OPT 变成了贪心解 → 贪心解最优

经典例子:活动选择(按结束时间排序)

证明:
  设 OPT 是按结束时间排序后选的第 1 个活动为 x
  贪心选的是结束最早的活动 a(f(a) ≤ f(x))
  把 OPT 里的 x 换成 a:
    - a 结束不晚于 x,所以后面的活动仍然可以安排
    - 活动数量不变
  → 存在包含 a 的最优解,贪心选择安全
  → 对剩余子问题递归应用

交换论证的模板:

存在一个最优解,它做了和贪心相同的第一个选择。

2. 数学归纳法

归纳假设: 前 k 步贪心选择是某个最优解的前 k 步
归纳步骤: 证明第 k+1 步贪心选择仍然可以是最优解的一部分

3. 拟阵(Matroid)理论

理论保证:如果问题的可行解集合构成一个拟阵,那么贪心一定最优。

拟阵(E,I)(E, \mathcal{I}) 满足:

  1. 非空性:∅∈I\emptyset \in \mathcal{I}
  2. 遗传性:A∈I,B⊆A⇒B∈IA \in \mathcal{I}, B \subseteq A \Rightarrow B \in \mathcal{I}
  3. 交换性:A,B∈I,∣A∣<∣B∣⇒∃e∈B∖A,A∪{e}∈IA, B \in \mathcal{I}, |A| < |B| \Rightarrow \exists e \in B \setminus A, A \cup \{e\} \in \mathcal{I}

满足这三条 → 按权重排序的贪心最优。

典型拟阵:

  • 图的生成森林(→ Kruskal 最小生成树的正确性)
  • 线性无关向量组

实用价值有限(判断是否是拟阵往往比直接证明还难),但知道"最小生成树能用贪心"是有理论依据的。

经典贪心问题

1. 活动选择(区间调度)

一堆区间[si,fi][s_i, f_i],选最多的互不重叠的区间。

贪心:按结束时间升序,能选就选。

struct Act { int s, f; };
sort(a.begin(), a.end(), [](const Act& x, const Act& y) { return x.f < y.f; });

int cnt = 0, lastEnd = -INF;
for (auto& x : a) {
    if (x.s >= lastEnd) {     // 不冲突
        cnt++;
        lastEnd = x.f;
    }
}

为什么按结束时间而不是开始时间或区间长度?因为结束越早,留给后面的空间越大。按长度排序会选到一个很长的区间堵死全场。

2. 区间覆盖

用最少的区间覆盖[1,T][1, T]。

贪心:每次在能覆盖当前点的区间里,选右端点最远的。

sort(a.begin(), a.end(), [](auto& x, auto& y) { return x.s < y.s; });
int cur = 1, i = 0, cnt = 0;
while (cur <= T) {
    int far = cur;
    while (i < n && a[i].s <= cur) far = max(far, a[i++].f);   // 能覆盖 cur 的里面挑最远
    if (far == cur) return -1;      // 无法推进,无解
    cur = far;
    cnt++;
}

3. Huffman 编码

构造最优前缀编码,使∑freqi⋅depthi\sum freq_i \cdot depth_i 最小。

贪心:每次合并频率最小的两个节点。

priority_queue<long long, vector<long long>, greater<long long>> pq;
for (long long f : freq) pq.push(f);
long long cost = 0;
while (pq.size() > 1) {
    long long a = pq.top(); pq.pop();
    long long b = pq.top(); pq.pop();
    cost += a + b;
    pq.push(a + b);
}

为什么对:频率最小的两个字符,在最优编码树中一定是最深层的兄弟节点(可交换论证)。

复杂度:O(nlog⁡n)O(n \log n)。

4. 最小生成树

  • Kruskal:按边权升序,不成环就加入(用并查集)
  • Prim:从一个点出发,每次加入连接"已选集合"和"未选集合"的最小边

两者都是贪心,正确性由**割性质(Cut Property)**保证:

对任意割,跨越该割的最小边一定在某棵最小生成树中。

// Kruskal
sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w < b.w; });
DSU dsu(n);
long long mst = 0;
for (auto& e : edges) {
    if (dsu.unite(e.u, e.v)) mst += e.w;
}

5. Dijkstra 最短路

每一步选"当前距离最小的未确定节点",因为它的距离不可能再被改进(前提:边权非负)。

为什么边权非负是关键:如果有负边,后面可能出现一条经过负边的更短路径,那么"当前最小"就不是最终值了 → 贪心失效 → 必须用 Bellman-Ford。

6. 分数背包

物品可以切分,求最大价值。

贪心:按性价比(价值/重量)降序,能装多少装多少。

sort(items.begin(), items.end(), [](auto& a, auto& b) {
    return (double)a.v / a.w > (double)b.v / b.w;
});
double ans = 0;
for (auto& it : items) {
    if (cap >= it.w) { ans += it.v; cap -= it.w; }
    else { ans += (double)it.v * cap / it.w; break; }
}

对比 0-1 背包:可切分时贪心对(因为不会有"装了 A 就装不下 B+C"的问题,A 可以只装一部分),不可切分时贪心错。

7. 任务调度( minimizing 平均完成时间)

nn 个任务,处理时间tit_i,安排顺序使平均等待时间最小。

贪心:按处理时间升序(短作业优先,SJF)。

证明:交换相邻的两个任务i,ji, j(ti>tjt_i > t_j),交换前后:

交换前: ... i j ...   贡献 = (T + t_i) + (T + t_i + t_j)
交换后: ... j i ...   贡献 = (T + t_j) + (T + t_j + t_i)

差值 = (交换前) - (交换后) = t_i - t_j > 0
→ 交换后更优

交换论证的典型应用:只看相邻两个元素交换后的变化,证明"逆序对"总能被改进 → 有序时最优。

8. 找零 / 货币系统

用最少的硬币凑出金额。

贪心(面额从大到小)只对特定面额系统成立(如人民币、美元的 canonical system)。

反例:面额 {1, 3, 4},凑 6:

  • 贪心:4 + 1 + 1 = 3 枚
  • 最优:3 + 3 = 2 枚

通用解法是 DP,不是贪心。贪心能用是巧合(面额系统的特殊性质),不是通法。

贪心的常见"贪法"

排序键典型问题
结束时间升序区间调度(选最多不重叠区间)
开始时间升序 + 选最远右端区间覆盖(最少区间覆盖)
右端点升序最少箭矢射气球、无重叠区间移除
价值/重量降序分数背包
处理时间升序最短作业优先调度
边权升序Kruskal MST
差值降序某些配对问题

找排序键是贪心的核心——通常是"哪个量决定了后续选择的空间"。

贪心 vs DP 怎么选

问自己: 做第一个选择时,需不需要考虑它对后面的影响?

不需要(做了这个选择,子问题结构不变且仍然最优)→ 贪心
需要(这个选择会影响后续的最优性)                → DP

实用判断流程:

  1. 先想贪心策略
  2. 立刻尝试构造反例(尤其是"占用资源导致后续无法搭配"的情况)
  3. 找不到反例 → 尝试交换论证证明
  4. 证明卡住 → 可能其实需要 DP

警惕:很多"看起来能贪心"的题其实是 DP。典型的陷阱:

  • 0-1 背包(贪心错,DP 对)
  • 找零(一般面额系统要用 DP)
  • 最长上升子序列(贪心只能求长度,用二分优化;求具体方案要 DP)

常见坑

  • 样例过了就以为对了:贪心的反例往往需要精心构造。务必自己构造边界数据
  • 贪心策略选错:按开始时间 vs 结束时间 vs 长度,结果完全不同
  • 相等元素的处理:贪心排序时相等怎么排?有时需要第二关键字
  • 贪心 + 反悔:有些问题需要"贪心 + 反悔堆"(如"课程表 III")——先贪心选,后面用更优的替换。这已经不是纯贪心了
  • 排序稳定性:如果贪心依赖原顺序,排序可能破坏它
  • 整数溢出:贪心常用求和,int 容易爆
  • 贪心求的是"一个"最优解:如果需要输出所有最优解或字典序最小的方案,要额外处理