贪心算法
#算法 · #贪心 · #区间调度 · #Huffman · #最优子结构
贪心算法在每一步都做"当前看起来最好的选择"，期望最终得到全局最优。它的核心挑战不在于算法本身，而在于证明贪心策略的正确性。
1. 贪心思想
1.1 什么是贪心
贪心算法是一种在每一步选择中都采取当前状态下局部最优的决策，从而希望导致全局最优结果的算法策略。
mermaid
flowchart TB
subgraph DP["动态规划"]
D1["考虑所有子问题"] --> D2["选择最优子结构组合"]
end
subgraph Greedy["贪心算法"]
G1["做当前最优选择"] --> G2["不回溯，一路走到黑"]
end核心区别：
- DP：先解决子问题，再选择 → 需要存储子问题结果
- 贪心：先做选择，再解决唯一子问题 → 不需要额外空间
1.2 贪心的适用条件
贪心适用的问题必须具备两个关键性质：
| 性质 | 说明 | 示例 |
|---|---|---|
| 贪心选择性质 | 局部最优选择能导致全局最优解 | 活动选择：选最早结束的活动不会错过更优解 |
| 最优子结构 | 问题的最优解包含子问题的最优解 | 做出贪心选择后，剩余子问题仍可用贪心求解 |
注意：贪心选择性质不是显然的，每道贪心题都必须证明。面试中至少要能说明"为什么这么做是对的"。
2. 正确性证明方法
2.1 交换论证（Exchange Argument）
核心思路：假设存在一个最优解，通过一系列"交换"操作，将它变成贪心解，且不降低解的质量。
经典例子 — 活动选择问题：
给定 n 个活动，每个有开始时间 s_i 和结束时间 f_i。选择最大数量的互不重叠的活动。
贪心策略：每次选结束时间最早的活动。
证明：
- 令最优解为 O = {o₁, o₂, ..., oₖ}，贪心解为 G =
- 设 g₁ 为结束最早的活动，若 o₁ ≠ g₁，则 f(g₁) ≤ f(o₁)（贪心选择了最早结束的）
- 将 o₁ 替换为 g₁，g₁ 结束更早，不会与 O 中后续活动冲突 → 仍然合法且数量不变
- 递归地对剩余活动应用此论证 → G 至少与 O 一样优
2.2 反证法
假设贪心解不是最优解，推导出矛盾。
2.3 数学归纳法
- 归纳基础：第一次贪心选择是正确的（或存在最优解包含该选择）
- 归纳步骤：假设前 k 步正确，证明第 k+1 步也正确
2.4 证明模板
1. 设贪心解 G = [g₁, g₂, ..., gₖ]
2. 设最优解 O = [o₁, o₂, ..., oₘ]（按某种顺序排列，使其能与 G 对齐）
3. 比较 g₁ 和 o₁，利用贪心策略的性质证明 g₁ "不差于" o₁
4. 将 o₁ 替换为 g₁，论证替换后仍为合法解
5. 递归重复 → 贪心解不差于最优解 → 贪心解即为最优解2.5 拟阵（Matroid）— 贪心算法的理论基础
拟阵理论回答了根本问题：为什么有些问题可以用贪心，有些不能？ 理解拟阵能让你一眼分辨贪心是否适用。
定义
一个拟阵 M = (S, I)，其中 S 是有限集，I 是 S 的子集族（称为独立集），满足三条公理：
- 非空性：∅ ∈ I（空集是独立的）
- 遗传性：若 A ∈ I 且 B ⊆ A，则 B ∈ I（独立集的子集也是独立的）
- 交换性：若 A, B ∈ I 且 |A| < |B|，则 ∃x ∈ B\A 使 A∪{x} ∈ I
直观理解：
S = 所有边，I = 不构成环的边集
→ 这就是"图拟阵"（Graphic Matroid）
→ 在这种拟阵上，贪心选择权重最小的边 = Kruskal 算法 ✅ 保证最优带权拟阵贪心算法
输入: 拟阵 M = (S, I), 权重 w: S → R
输出: 最大权独立集
1. 将 S 按权重降序排列
2. A = ∅
3. for each x in S (按序):
4. if A ∪ {x} ∈ I:
5. A = A ∪ {x}
6. return A核心定理：对于任意拟阵，上述贪心算法总能得到最大权重独立集。这意味着只要问题能被建模为拟阵，贪心就是最优的。
哪些问题能用拟阵建模？
| 问题 | 拟阵类型 | S | I |
|---|---|---|---|
| 最小生成树 | 图拟阵 | 所有边 | 不构成环的边集 |
| 最大独立集 | — | 顶点集 | 独立集 |
| 活动选择 | 区间拟阵 | 所有区间 | 互不重叠区间集 |
| 线性无关向量选择 | 线性拟阵 | 向量组 | 线性无关向量组 |
| Huffman 编码 | —（非拟阵，但有特殊结构） | — | — |
为什么 0-1 背包不是拟阵？
S = {item1(3kg,$5), item2(2kg,$3), item3(2kg,$3)}
I = 总重量 ≤ 5kg 的物品组合
交换性不成立：
A = {item1} (3kg, ∈ I, |A|=1)
B = {item2,item3} (4kg, ∈ I, |B|=2)
|B| > |A|，但无法将 B 中任何元素加入 A 而不超重！
→ 交换性破坏 → 不是拟阵 → 贪心不一定最优 ❌一句话总结：如果问题可以形式化为拟阵，贪心就是最优解。否则需要更复杂的工具（DP、分支限界等）。
3. 经典问题
3.1 活动选择 / 区间调度
问题：选择最多数量的互不重叠区间。
贪心策略：按结束时间排序，每次选最早结束且不冲突的区间。
go
// 活动选择 — O(n log n)
func maxActivities(start, finish []int) int {
n := len(start)
// 按结束时间排序
type Activity struct{ s, f int }
acts := make([]Activity, n)
for i := range start {
acts[i] = Activity{start[i], finish[i]}
}
sort.Slice(acts, func(i, j int) bool { return acts[i].f < acts[j].f })
count := 1
lastEnd := acts[0].f
for i := 1; i < n; i++ {
if acts[i].s >= lastEnd {
count++
lastEnd = acts[i].f
}
}
return count
}为什么不能按开始时间排序？ 反例：[1, 10] 和 [2, 3]，按开始时间会选 [1,10]，只能 1 个；但选 [2,3] 可以选完后继续。
3.2 区间覆盖 / 跳跃游戏 II
问题：最少需要几个区间覆盖整个线段。
贪心策略：在能覆盖当前起点的区间中，选右端点最远的。
go
// 跳跃游戏 II — 最少跳跃次数到达终点
// nums[i] 表示从位置 i 最多能跳的距离
// 用区间覆盖的视角：每个位置 i 对应区间 [i, i+nums[i]]
func jump(nums []int) int {
n := len(nums)
if n <= 1 {
return 0
}
jumps, curEnd, farthest := 0, 0, 0
for i := 0; i < n-1; i++ {
farthest = max(farthest, i+nums[i])
if i == curEnd {
jumps++
curEnd = farthest
if curEnd >= n-1 {
break
}
}
}
return jumps
}3.3 Huffman 编码
问题：给定字符频率，构造前缀码使编码总长度最短。
贪心策略：每次选频率最小的两个节点合并。
go
// Huffman 编码（伪框架）
// 使用最小堆：每次取两个最小频率的节点合并，将合并结果放回堆
// 重复直到堆中只剩一个节点（Huffman 树的根）正确性：可以通过交换论证证明。任何最优解中，频率最小的两个字符一定在树的最底层、且互为兄弟。
3.4 分数背包
问题：每个物品可以取一部分。容量 W 下最大化总价值。（0-1 背包物品不可分割，只能用 DP）
贪心策略：按单位重量价值降序取。
go
// 分数背包 — O(n log n)
type Item struct{ weight, value float64 }
func fractionalKnapsack(items []Item, capacity float64) float64 {
sort.Slice(items, func(i, j int) bool {
return items[i].value/items[i].weight > items[j].value/items[j].weight
})
total := 0.0
for _, it := range items {
if capacity <= 0 {
break
}
take := min(capacity, it.weight)
total += take * (it.value / it.weight)
capacity -= take
}
return total
}3.5 加油站问题
问题：环形路线，gas[i] 是补给量，cost[i] 是消耗量。找能绕一圈的起点。
go
func canCompleteCircuit(gas []int, cost []int) int {
total, cur, start := 0, 0, 0
for i := 0; i < len(gas); i++ {
diff := gas[i] - cost[i]
total += diff
cur += diff
if cur < 0 {
// 从 start 到 i 的任何点出发都会在这里失败
start = i + 1
cur = 0
}
}
if total < 0 {
return -1
}
return start
}贪心证明：如果从 A 出发到不了 B（AB 之间任意一点都不行），那么 AB 之间的任何一点也都到不了 B。因此可以直接跳过整个失败段。
3.6 找零钱问题
问题：用最少硬币数凑出金额。贪心适用条件：硬币面值具有"规范"性质（倍数关系）。
go
// 贪心找零 — 仅当面值为 [1, 5, 10, 25] 等规范面值时正确
func coinChange(coins []int, amount int) []int {
sort.Sort(sort.Reverse(sort.IntSlice(coins)))
result := make([]int, len(coins))
for i, c := range coins {
result[i] = amount / c
amount %= c
}
return result
}注意：对于任意面值（如
[1, 3, 4]凑 6），贪心给出4+1+1=3枚，但最优是3+3=2枚。此时必须用 DP。
4. 贪心 vs DP：判断技巧
| 特征 | 倾向贪心 | 倾向 DP |
|---|---|---|
| 选择后子问题数量 | 只有 1 个子问题 | 多个子问题需要比较 |
| 全局最优性质 | 局部最优可直接推导全局最优 | 局部最优不等于全局最优 |
| 典型标志 | 可排序后贪心、可维护堆 | 状态转移、子问题重叠 |
| 时间复杂度 | O(n log n) | O(n²) 或 O(n³) |
快速判断清单：
- 能否排序后贪心？→ 试一试，找个反例
- 如果找不到反例 → 尝试证明（交换论证）
- 如果找到反例 → 用 DP
5. 更多贪心问题速查
| 问题 | 贪心策略 | 复杂度 |
|---|---|---|
| 会议室 II（最少会议室） | 按开始时间排序 + 最小堆维护结束时间 | O(n log n) |
| 合并区间 | 按开始排序，遍历合并 | O(n log n) |
| 删除重叠区间 | 按结束时间排序，保留结束最早的 | O(n log n) |
| 划分字母区间 | 记录每个字符最后出现位置，不断扩展右边界 | O(n) |
| 种花问题 | 从左到右能种就种 | O(n) |
| 分发糖果 | 左遍历 + 右遍历 | O(n) |
| 用最少数量的箭引爆气球 | 按结束坐标排序 | O(n log n) |
| Dijkstra 最短路径 | 每次选距离最小的节点 | O((V+E)log V) |
6. 工程中的贪心思想
| 场景 | 贪心体现 |
|---|---|
| TCP 拥塞控制 | 每次 ACK 增大 cwnd（AIMD），不回溯验证 |
| Redis LRU 淘汰 | 采样近似：随机取 N 个 key，淘汰最久未用的 |
| LSM-Tree Compaction | 按层优先级合并，不追求全局最优排序 |
| Go GC | 三色标记 + 混合写屏障，不追求完美引用追踪 |
| 负载均衡 | 最少连接/加权轮询，贪心选择当前最优节点 |
6.1 为什么 Dijkstra 是贪心算法？—— 完整证明
Dijkstra 最短路径算法是最经典的贪心案例之一，但很多人只记结论不记证明。这里给出完整的交换论证：
问题：给定带非负权重的有向图 G = (V,E) 和源点 s，求 s 到所有其他顶点的最短路径。
贪心策略：每次选择当前距离估计最小的未处理顶点，松弛其出边。
go
func dijkstra(graph [][]Edge, s int) []int {
n := len(graph)
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt
}
dist[s] = 0
visited := make([]bool, n)
for i := 0; i < n; i++ {
// 贪心：选最小的 dist 值（当前局部最优）
u := -1
minDist := math.MaxInt
for v := 0; v < n; v++ {
if !visited[v] && dist[v] < minDist {
minDist, u = dist[v], v
}
}
if u == -1 {
break
}
visited[u] = true
// 松弛：尝试用 u 更新邻居
for _, e := range graph[u] {
if dist[u]+e.w < dist[e.v] {
dist[e.v] = dist[u] + e.w
}
}
}
return dist
}为什么贪心选择是正确的？— 反证法证明：
定理：当 Dijkstra 从优先队列中取出顶点 u 时，dist[u] 已经是 s→u 的最短路径。
证明（反证法）：
设 u 是第一个被"错误取出"的顶点，即 dist[u] > 真正的 δ(s, u)。
令 P 为 s→u 的真正最短路径。由于 s 的 dist 正确（dist[s]=0=δ(s,s)），
P 上必然存在一条边 (x, y)，其中：
- x 在 u 被取出前已被正确取出（dist[x] = δ(s,x)）
- y 在 u 被取出前尚未被取出
由于 y 在 s→u 的最短路径上且在 u 之前：
δ(s, y) ≤ δ(s, u) （y 在最短路径上比 u 更靠近 s）
又因为所有边权重非负（这个前提至关重要！）：
δ(s, y) ≤ δ(s, u) < dist[u] ← 矛盾！
因为 Dijkstra 选择 dist 最小的未处理顶点：
如果 dist[y] = δ(s, y) < dist[u]，应该在 u 之前取出 y！
但 y 尚未被取出 → 说明 dist[y] 还没被正确更新 → 说明 x 松弛 y 时出了问题
然而 x 已正确取出，在取出时已松弛过 (x, y) 边：
dist[y] ≤ dist[x] + w(x,y) = δ(s,x) + w(x,y) = δ(s,y)
而 dist[y] ≥ δ(s,y) 显然成立 → dist[y] = δ(s,y) < dist[u]
→ y 应该在 u 之前被取出，与假设矛盾 ■这个证明揭示了贪心成立的关键前提：
- ✅ 非负权重：保证后续顶点不会缩短已确定顶点的路径
- ❌ 若有负权边：Dijkstra 贪心失效 → 必须用 Bellman-Ford
6.2 贪心在图论中的更多应用
mermaid
flowchart TB
subgraph MST["最小生成树 (MST)"]
Kruskal["Kruskal: 每次选最小权边<br/>（只要不构成环）"]
Prim["Prim: 每次伸展最小权邻边<br/>（从已选点集出发）"]
end
subgraph ShortestPath["最短路径"]
Dijkstra["Dijkstra: 每次选最近的点"]
A_star["A*: Dijkstra + 启发式预估"]
end
subgraph Other["其他图论贪心"]
Topological["拓扑排序: 每次选入度为0"]
Coloring["贪心着色: 按序分配最小可用色"]
Dominating["支配集: 贪心选最大度"]
endKruskal 的贪心证明（拟阵角度）
图拟阵 M = (E, I)，其中 E = 所有边，I = 不含环的边集
贪心算法: 按权重升序取边，如果加入后仍 ∈ I（即不构成环）就加入。
根据拟阵贪心定理 → 得到的是最大权独立集。
但我们需要的是"最小生成树" = "最小权极大独立集"。
转换: 对每条边 e 定义权重 w'(e) = W_max - w(e)
（W_max 是最大的边权，反转权重方向）
则"最大 w' 独立集" = "最小 w 极大独立集" = MST ■Prim 的贪心正确性（剪枝证明）
定理: 设 T 是通过 Prim 算法逐步构建的树。在每一步选取的
最小权边 (u,v)（其中 u ∈ T, v ∉ T）一定属于某棵 MST。
证明（剪枝法）:
设某棵 MST 包含 T 但不包含 (u,v)。
在 MST 中，必然存在另一条边 e 连接 T 和 V\T。
根据 Prim 的选择: w(u,v) ≤ w(e)。
将 e 替换为 (u,v)，仍为生成树，且总权不增。
→ 存在一棵包含 (u,v) 的 MST ■A* 算法 — 强化版的贪心
A* = Dijkstra + 启发式函数 h(v)（预估 v 到终点的成本）
优先队列键值: f(v) = g(v) + h(v)
g(v) = s→v 的已知最短距离（Dijkstra 的 dist）
h(v) = v→t 的预估距离（启发式）
要求:
- h(v) 可容许（Admissible）: h(v) ≤ 真实距离（不过高估计）
- h(v) 一致（Consistent）: h(u) ≤ w(u,v) + h(v)（三角不等式）
当 h(v) = 0: 退化为 Dijkstra
当 h(v) = 真实距离: 直接找到最优解（不需要探索无关节点）
应用: 游戏寻路、地图导航、机器人路径规划| 算法 | 贪心选择 | 时间复杂度 | 适用图 | 非负权重 |
|---|---|---|---|---|
| Kruskal | 最小权重边 | O(E log E) | 无向（稀疏） | ✅ 可 |
| Prim | 最小权重邻边 | O((V+E)log V) | 无向（稠密） | ✅ 可 |
| Dijkstra | 最近距离顶点 | O((V+E)log V) | 有向/无向 | ✅ 必须 |
| Bellman-Ford | —（DP，非贪心） | O(VE) | 有向/无向 | 可负 |
| A* | f(v)=g(v)+h(v) 最小 | ≤ Bellman-Ford | 有向/无向 | ✅ 必须 |
7. 常见错误
| 错误 | 说明 |
|---|---|
| 不证明就用贪心 | 面试必问"为什么贪心是对的"，答不上来直接减分 |
| 错误使用贪心 | 0-1 背包、最长递增子序列等不可贪心，必须 DP |
| 忽略排序 | 很多贪心需要预排序（按某个维度），忘记排序导致错误 |
| 贪心策略错误 | 同一问题可能有多个贪心候选，需要验证哪个正确 |
参考
- CLRS（《算法导论》）第 16 章：贪心算法
- Hello 算法 第 11 章：贪心
- LeetCode 贪心专题
登录后即可发表评论 👇