贪心法（Greedy Approach）

北京大学《算法设计与分析》课程第6讲，屈婉玲

文字版PDF，67页，pdftotext全文提取

一、基本思想

适用问题

组合优化问题，满足优化原则（最优子结构）
多步判断求解，解为判断序列
选择依据：是否满足约束条件 + 局部优化测度

核心问题

是否可以得到最优解？
不能得到最优解时，解与最优解的误差估计

经典实例

最小生成树 Kruskal 算法
活动选择问题

二、贪心算法设计

设计要素

适用条件：满足优化原则的组合优化问题，求解可表示为多步判断
贪心选择：确定一个优化测度（贪心选择依据），不考虑以前的选择，只与当前状态有关
贪心选择性质：具有该性质则得到最优解，否则为近似解
自顶向下计算：通过贪心选择将原问题规约为子问题
线性表记录：记录选择结果

正确性证明方法

1. 数学归纳法

对步数 k 归纳：对于任意 k，k 步贪心选择得到 i₁, i₂, …, i_k，则存在最优解包含 i₁, i₂, …, i_k
对规模 k 归纳：对于任意 k，贪心法得到关于规模为 k 的问题的最优解

2. 交换论证

在保证最优性不变的前提下，从一个最优解出发进行逐步替换，最终得到贪心法的解

与动态规划法的比较

贪心：自顶向下，每步做局部最优选择，不回溯
DP：自底向上，从子问题的最优解构造父问题的最优解
贪心的关键：证明贪心选择性质（每步最优选择通向全局最优）

三、应用实例

实例1：活动选择问题

问题：n 项活动，每项有开始时间 s_i 和结束时间 f_i，活动 i 与 j 相容当且仅当 s_i ≥ f_j 或 s_j ≥ f_i，求最大的两两相容活动集。

贪心策略：按结束时间递增排序，依次选择（结束最早的优先）

算法 Greedy Select：

1. n ← length[S]
2. A ← {1}
3. j ← 1
4. for i ← 2 to n
5.    if s_i ≥ f_j
6.       then A ← A ∪ {i}; j ← i
7. return A

正确性证明：对步数归纳

归纳基础：存在最优解包含活动1（若最优解第一个活动为 j≠1，用活动1替换 j，仍是最优解）
归纳步骤：假设前 k 步选择 i₁, …, i_k 都在最优解中，则第 k+1 步选择 i_{k+1} 也在某个最优解中

实例：

活动	1	2	3	4	5	6	7	8	9	10	11
s_i	1	3	0	5	3	5	6	8	8	2	12
f_i	4	5	6	7	8	9	10	11	12	13	14

解：A = {1, 4, 8, 11}，总结束时间 t = 14

实例2：最优装载（Loading）

问题：n 个集装箱装上轮船，重量限制为 c，无体积限制，求最多装多少个集装箱。

数学模型：

max Σ x_i
Σ w_i x_i ≤ c
x_i ∈ {0, 1}

贪心策略：按重量从轻到重排序，轻者先装

正确性证明：对规模归纳

归纳基础：n = 1 时显然最优
归纳步骤：假设 n−1 个集装箱贪心法最优，则 n 个时，先装最轻的 1 号，剩下的 n−1 个在 c−w₁ 容量下用贪心法也最优

复杂度：O(n log n)（主要为排序）

说明：Loading 是 0-1 背包的特例（v_i = 1），0-1 背包是 NP 难的，但此特例可在 O(n log n) 时间解决。

实例3：最小延迟调度

问题：任务集合 S，每个任务有截止时间 d_i 和加工时间 t_i，一个调度 f: S→N（f(i) 为开始时间），求使最大延迟最小的调度，即 min max(f(i) + t_i − d_i)。

三种贪心策略对比：

按加工时间 t_i 从小到大 —— 不能得到最优解
- 反例：t₁=1, d₁=100; t₂=10, d₂=10
按 d_i − t_i 从小到大 —— 不能得到最优解
- 反例：t₁=1, d₁=2; t₂=10, d₂=10
按截止时间 d_i 从小到大 —— 最优

算法：

1. 按 d₁ ≤ d₂ ≤ … ≤ d_n 排序
2. f(1) ← 0
3. for i ← 2 to n
4.    f(i) ← f(i−1) + t_{i−1}

正确性证明：交换论证

命题1：所有没有逆序、没有空闲时间的调度具有相同的最大延迟
- 逆序 (i,j)：f(i) < f(j) 且 d_i > d_j
交换论证步骤：
1. 若最优调度有逆序，则存在相邻逆序 (i, i+1)
2. 交换相邻逆序 i 和 j，逆序数减 1，且不增加最大延迟
  - 交换对其他任务无影响
  - 交换后 j 的延迟不增加
  - i 在 f₂ 的延迟 = j 在 f₁ 的结束时间 − d_i < j 在 f₁ 的延迟（因为 d_j < d_i）
3. 至多 n(n−1)/2 次交换得到无逆序的最优调度

四、贪心法得不到最优解的处理

方法一：确定最优解的输入条件

找零钱问题：n 种零钱，重量 w_i，价值 v_i，付 y 元，求总重量最轻。

贪心算法：假设 w₁/v₁ ≥ w₂/v₂ ≥ … ≥ w_n/v_n（单位价值重量递减），从大面值开始尽可能多用

动态规划算法：F_k(y) 表示用前 k 种零钱总钱数 y 的最小重量

F_{k+1}(y) = min { F_k(y − v_{k+1} x_{k+1}) + w_{k+1} x_{k+1} }
F₁(y) = w₁ y / v₁

判定定理（n > 2 时）：假定 G_k(y) = F_k(y)，且 v_{k+1} > v_k，v_{k+1} = p v_k − δ（0 ≤ δ < v_k, p∈Z⁺），则以下命题等价：

G_{k+1}(y) ≤ G_k(y)
G_{k+1}(y) = F_{k+1}(y)
G_{k+1}(p v_k) = F_{k+1}(p v_k)
w_{k+1} + G_k(δ) ≤ p w_k

验证所有 n 种零钱需 O(n²) 时间。

实例：v = {1, 5, 14, 18}, w_i = 1

v₃ = 14 = 3×5 − 1，w₃ + G₂(1) = 1+1 = 2 ≤ 3×1 = 3 → G₃最优
v₄ = 18 = 2×14 − 10，w₄ + G₃(10) = 1+2 = 3 > 2×1 = 2 → G₄非最优
- 反例：y=28，G₄(28)=⌊28/18⌋+⌊10/5⌋=1+2=3，F₄(28)=28/14=2

方法二：近似解误差估计

装箱问题：n 个物体 a_i ≤ 1，装入长为 1 的箱子，求最少箱子数。

算法1：下次适合法 NF（Next Fit）

只看当前箱子，放不下就开新箱
渐近比 r(NF) = 2
上界证明：任意两个相邻箱子的装入量之和 > 1，故总量 > (m−1)/2，最优 L* > (m−1)/2，得 NF(L) < 2L* + 1
下界构造：交替放入 1/2 和 1/(2N) 的物体，NF 用 2N 箱，最优用 N+1 箱

算法2：首次适合法 FF（First Fit）

依次检查每个已有箱子，第一个能放下就放
渐近比 r(FF) = 1.7
17/10 L* − 2 ≤ FF(L) ≤ 17/10 L* + 2

算法3：递降首次适合法 FFD（First Fit Decreasing）

先按物体大小从大到小排序，再用 FF
渐近比 r(FFD) = 11/9 ≈ 1.22
11/9 L* ≤ FFD(L) ≤ 11/9 L* + 4

五、最优前缀码（Huffman 编码）

前缀码：任何字符的代码都不能作为其他字符代码的前缀

用二叉树表示，字符为树叶，代码为根到叶的路径

问题：n 个字符 x_i，频率 f(x_i)，求平均位数最小的前缀码。

Huffman 算法

Huffman(C):
1. n ← |C|
2. Q ← C          // 按频率递增的优先队列
3. for i ← 1 to n−1 do
4.    z ← Allocate-Node()
5.    z.left ← Extract-Min(Q)
6.    z.right ← Extract-Min(Q)
7.    f[z] ← f[x] + f[y]
8.    Insert(Q, z)
9. return Q

时间复杂度：O(n log n)

实例：a:45, b:13, c:12, d:16, e:9, f:5

编码：a=1, b=011, c=010, d=001, e=0001, f=0000
平均位数：4×(0.05+0.09) + 3×(0.16+0.12+0.13) + 1×0.45 = 2.24

正确性证明（对规模 n 归纳）

引理1：设 C 是字符集，x, y 是频率最小的两个字符，则存在最优前缀码使得 x, y 码字等长，且仅最后一位不同。

证明：将最优树中最深层的两个树叶 a, b 与 x, y 交换，权不会增加

引理2：设 T 是前缀码对应的二叉树，x, y 是最深层兄弟树叶，z 是它们的父节点，令 f(z) = f(x) + f(y)，C’ = (C − {x,y}) ∪ {z}，T’ 对应 C’ 的树，则 B(T) = B(T’) + f(x) + f(y)

归纳证明：

归纳基础：n = 2 显然成立
归纳步骤：假设规模为 k 时最优，考虑 k+1 个字符，取频率最小的 x₁, x₂，合并为 z 得规模为 k 的 C’，由归纳假设 Huffman 算法得 T’ 最优，将 x₁, x₂ 作为 z 的儿子得 T，T 必为最优（否则与 T’ 的最优性矛盾）

六、文件归并（最优二叉归并树）

问题：n 个已排序文件，用二分归并合成一个文件，求比较次数最少的归并次序。

归并代价：归并两个大小为 f_i 和 f_j 的文件，代价为 |f_i| + |f_j|

总代价 = 所有内结点权之和 = Σ |f_k| × depth(f_k)（叶节点的深度）

算法：Huffman 树算法（每次合并最小的两个文件）

时间：O(n log n)
正确性：仿照 Huffman 树的证明

实例：文件 26, 10, 63, 19, 33, 21

普通归并代价：36 + 82 + 54 + 118 + 172 = 462
Huffman 最优归并代价：29 + 62 + 47 + 109 + 63 = 419（更优）

七、最小生成树

Prim 算法

思想：从一个顶点出发，每次选连接 S 和 V−S 的最小权边加入

Prim(G, E, W):
1. S ← {1}
2. while V − S ≠ ∅ do
3.    从 V−S 中选 j 使 j 到 S 中顶点的边权最小
4.    S ← S ∪ {j}

正确性证明：对步数归纳

归纳基础：k=1，存在 MST 包含关联顶点 1 的最小权边
- 若 MST T 不含 {1,i}，则 T ∪ {{1,i}} 含回路，换掉回路中另一条关联 1 的边，得到 T’，W(T’) ≤ W(T)
归纳步骤：假设前 k−1 步边都在某个 MST T 中，第 k 步选边 e_k，若 T 不含 e_k，则加 e_k 形成回路，换掉回路中另一条跨 S 和 V−S 的边 e，得 T*，W(T*) ≤ W(T)

时间复杂度：O(n²)（邻接矩阵）

Kruskal 算法

思想：按边权从小到大排序，依次加入不形成回路的边

Kruskal(G, W):
1. 按权从小到大排序边：e₁, e₂, …, e_m
2. for i ← 1 to m do
3.    若 e_i 的两端点不在同一连通分支，则加入 T

正确性证明：对顶点数归纳

归纳基础：n = 2 显然成立
归纳步骤：设 n 个顶点时算法正确，考虑 n+1 个顶点的图 G，取最小权边 e = {i,j}，短接 i 和 j 得 n 顶点图 G’，由归纳假设算法得 G’ 的 MST T’，则 T = T’ ∪ {e} 是 G 的 MST

时间复杂度：O(m log m)

八、单源最短路径（Dijkstra 算法）

问题：带权图（非负权），源点 s，求 s 到所有其他顶点的最短路径。

算法

Dijkstra(G, E, W):
1. S = {s}; dist[s] ← 0
2. for i ∈ V − {s} do
3.    dist[i] ← w(s, i)   // 无边则为 ∞
4. while V − S ≠ ∅ do
5.    从 V−S 取相对 S 最短路径的顶点 j
6.    S ← S ∪ {j}
7.    for i ∈ V − S do
8.       dist[i] ← min(dist[i], dist[j] + w(j,i))

S：已确定最短路径的顶点集合
dist[u]：从 s 到 u 相对于 S 的最短路径（只经过 S 中顶点）

正确性证明（对步数归纳）

命题：算法第 k 步时，对 S 中每个结点 i，dist[i] = short[i]（真正的最短路径长度）

归纳基础：k=1，S={s}，dist[s] = short[s] = 0 ✓
归纳步骤：假设前 k 步为真，第 k+1 步选顶点 v。假若存在另一条 s→v 路径 L，第一次出 S 的顶点为 x，第一个 V−S 中的顶点为 y，则：
- dist[v] ≤ dist[y]（v 先被选）
- dist[v] ≤ dist[y] + d(y,v) ≤ L
- 故 dist[v] = short[v]

时间复杂度：O(n²)（邻接矩阵）

九、贪心法小结

设计要素

适用于满足优化原则的组合优化问题
问题可表示为多步判断
确定一个优化测度——贪心选择的依据
确定是否满足贪心选择性质——每步贪心选择都导致最优解
自顶向下计算

正确性证明方法

数学归纳法
- 对步数 k 归纳
- 对问题规模 k 归纳
交换论证

得不到最优解的处理

讨论哪些输入能得到最优解（如找零钱问题的判定条件）
讨论最坏情况下的误差估计（如装箱问题的渐近比）

复杂度

时间复杂度和空间复杂度都较低（通常 O(n log n) 或 O(n²)）

十大经典贪心算法速查表

问题	贪心策略	正确性证明	复杂度
活动选择	按结束时间早优先	步数归纳	O(n log n)
最优装载	按重量从轻到重	规模归纳	O(n log n)
最小延迟调度	按截止时间早优先	交换论证	O(n log n)
找零钱	大面值优先	定理判定	O(n)
装箱 NF	下次适合	误差估计 r=2	O(n)
装箱 FFD	大物体优先+首次适合	误差估计 r=11/9	O(n log n)
最优前缀码	两小合并（Huffman）	规模归纳	O(n log n)
文件归并	两小合并（Huffman树）	规模归纳	O(n log n)
最小生成树 Prim	最近顶点加入	步数归纳	O(n²)
最小生成树 Kruskal	按边权从小到大	规模归纳	O(m log m)
单源最短路径 Dijkstra	最近顶点扩展	步数归纳	O(n²)

知识库

探索

算法设计与分析 第6讲 - 贪心法

贪心法（Greedy Approach）

一、基本思想

适用问题

核心问题

经典实例

二、贪心算法设计

设计要素

正确性证明方法

1. 数学归纳法

2. 交换论证

与动态规划法的比较

三、应用实例

实例1：活动选择问题

实例2：最优装载（Loading）

实例3：最小延迟调度

四、贪心法得不到最优解的处理

方法一：确定最优解的输入条件

方法二：近似解误差估计

算法1：下次适合法 NF（Next Fit）

算法2：首次适合法 FF（First Fit）

算法3：递降首次适合法 FFD（First Fit Decreasing）

五、最优前缀码（Huffman 编码）

Huffman 算法

正确性证明（对规模 n 归纳）

六、文件归并（最优二叉归并树）

七、最小生成树

Prim 算法

Kruskal 算法

八、单源最短路径（Dijkstra 算法）

算法

正确性证明（对步数归纳）

九、贪心法小结

设计要素

正确性证明方法

得不到最优解的处理

复杂度

十大经典贪心算法速查表

相关课程

关系图谱

目录

反向链接

算法设计与分析第6讲 - 贪心法