Greedy
贪心在做什么
贪心(Greedy):每一步都做当前看起来最优的选择,不回头。
贪心: 局部最优 → 局部最优 → ... → 全局最优(?)
DP: 枚举所有选择,取全局最优核心难点:贪心不一定对。它的正确性必须证明,不能靠"感觉"和"样例过了"。
什么时候贪心是对的
需要两个性质:
- 贪心选择性质(Greedy Choice Property):可以从局部最优选择出发构造出全局最优解。即:第一个选择可以贪心地做,而不用考虑它对后续的影响。
- 最优子结构(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 → 总价值 48A 的性价比最高,但它占用了容量,导致后面两个都装不下。
证明方法
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)理论
理论保证:如果问题的可行解集合构成一个拟阵,那么贪心一定最优。
拟阵 满足:
- 非空性:
- 遗传性:
- 交换性:
满足这三条 → 按权重排序的贪心最优。
典型拟阵:
- 图的生成森林(→ Kruskal 最小生成树的正确性)
- 线性无关向量组
实用价值有限(判断是否是拟阵往往比直接证明还难),但知道"最小生成树能用贪心"是有理论依据的。
经典贪心问题
1. 活动选择(区间调度)
一堆区间,选最多的互不重叠的区间。
贪心:按结束时间升序,能选就选。
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. 区间覆盖
用最少的区间覆盖。
贪心:每次在能覆盖当前点的区间里,选右端点最远的。
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 编码
构造最优前缀编码,使 最小。
贪心:每次合并频率最小的两个节点。
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);
}为什么对:频率最小的两个字符,在最优编码树中一定是最深层的兄弟节点(可交换论证)。
复杂度:。
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 平均完成时间)
个任务,处理时间,安排顺序使平均等待时间最小。
贪心:按处理时间升序(短作业优先,SJF)。
证明:交换相邻的两个任务(),交换前后:
交换前: ... 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实用判断流程:
- 先想贪心策略
- 立刻尝试构造反例(尤其是"占用资源导致后续无法搭配"的情况)
- 找不到反例 → 尝试交换论证证明
- 证明卡住 → 可能其实需要 DP
警惕:很多"看起来能贪心"的题其实是 DP。典型的陷阱:
- 0-1 背包(贪心错,DP 对)
- 找零(一般面额系统要用 DP)
- 最长上升子序列(贪心只能求长度,用二分优化;求具体方案要 DP)
常见坑
- 样例过了就以为对了:贪心的反例往往需要精心构造。务必自己构造边界数据
- 贪心策略选错:按开始时间 vs 结束时间 vs 长度,结果完全不同
- 相等元素的处理:贪心排序时相等怎么排?有时需要第二关键字
- 贪心 + 反悔:有些问题需要"贪心 + 反悔堆"(如"课程表 III")——先贪心选,后面用更优的替换。这已经不是纯贪心了
- 排序稳定性:如果贪心依赖原顺序,排序可能破坏它
- 整数溢出:贪心常用求和,
int容易爆 - 贪心求的是"一个"最优解:如果需要输出所有最优解或字典序最小的方案,要额外处理