cover.png#贪心算法

贪心算法 (Greedy Algorithm) 做出当前看起来最优的选择，期望局部最优能导向全局最优

贪心适用的两个关键性质： 1. 贪心选择性质 (Greedy-choice property)：通过局部最优选择可以得到全局最优解。即在做选择时不必考虑子问题的解 2. 最优子结构 (Optimal substructure)：问题的最优解包含子问题的最优解

贪心 vs DP： - DP：自底向上，求解所有子问题后做选择（选择依赖子问题的解） - 贪心：自顶向下，先做贪心选择，然后求解剩余子问题（选择不依赖子问题的解） - 贪心可以看作 DP 的特殊情况：每个子问题只需考虑一种选择

贪心的两种证明技术： 1. “保持领先” (Stay Ahead)：证明贪心的每一步都不比最优解差 2. 交换论证 (Exchange Argument)：将最优解逐步变换为贪心解，不损失最优性

---

区间调度（活动选择）问题

问题定义

\(n\) 个活动 \(S = \{a_1, a_2, \ldots, a_n\}\)，活动 \(a_i\) 占用时间 \([s_i, f_i)\)，两个活动兼容当且仅当时间不重叠

目标：选出最大数量的互相兼容的活动子集

DP 思路

定义 \(S_{ij} = \{a_k \in S : f_i \leq s_k < f_k \leq s_j\}\)（在 \(a_i\) 结束后、\(a_j\) 开始前的活动集）

设 \(c[i,j]\) 为 \(S_{ij}\) 的最大兼容活动数：

\[c[i,j] = \begin{cases} 0 & S_{ij} = \emptyset \\ \max_{a_k \in S_{ij}} \{c[i,k] + c[k,j] + 1\} & S_{ij} \neq \emptyset \end{cases}\]

贪心策略的选择

策略	描述	最优？
最早开始时间	按 \(s_i\) 升序	否
最短区间	按 \(f_i - s_i\) 升序	否
最少冲突	按冲突数 \(c_i\) 升序	否
最早结束时间	按 \(f_i\) 升序	是

最早开始时间反例：

|————————————————————————|
  |——|  |——|  |——|  |——|

一个长活动从最早开始，覆盖了多个短活动。贪心选 1 个，最优可选 4 个

最短区间反例：

|—————|  |—————|
     |————|

短活动横跨两个长活动，选了短的反而排除两个长的。贪心选 1 个，最优可选 2 个

最少冲突反例：构造一组活动使得冲突最少的活动反而是错误选择

贪心算法

GREEDY-ACTIVITY-SELECTOR(s, f):
    按结束时间排序使 f₁ ≤ f₂ ≤ ... ≤ fₙ
    A ← {a₁}
    k ← 1
    for m = 2 to n:
        if s_m ≥ f_k:
            A ← A ∪ {a_m}
            k ← m
    return A

时间 \(O(n \log n)\)（排序主导，若已排序则 \(\Theta(n)\)）

贪心选择性质

定理 (CLRS Theorem 16.1)：存在一个最大兼容子集包含最早结束的活动 \(a_1\)

点击查看证明

设 \(A\) 是 \(S\) 的一个最大兼容子集，设 \(a_k\) 是 \(A\) 中结束时间最早的活动

若 \(a_k = a_1\)，证毕

若 \(a_k \neq a_1\)，构造 \(A' = A \setminus \{a_k\} \cup \{a_1\}\)

由于 \(f_1 \leq f_k\)（\(a_1\) 是全局最早结束的），\(a_1\) 与 \(A \setminus \{a_k\}\) 中的所有活动兼容（\(a_k\) 兼容，\(a_1\) 结束得更早，更不可能冲突）

因此 \(A'\) 也是最大兼容子集，且包含 \(a_1\)

最优子结构

选择 \(a_1\) 后，原问题转化为子问题：在 \(S' = \{a_i \in S : s_i \geq f_1\}\) 中找最大兼容子集

定理：若 \(A\) 是包含 \(a_1\) 的最大兼容子集，则 \(A' = A \setminus \{a_1\}\) 是 \(S'\) 的最大兼容子集

点击查看证明

反证：若 \(A'\) 不是 \(S'\) 的最大兼容子集，存在 \(B' \subseteq S'\)，\(|B'| > |A'|\)，\(B'\) 中活动互相兼容

则 \(B' \cup \{a_1\}\) 是 \(S\) 的兼容子集（\(a_1\) 与 \(B'\) 中所有活动兼容，因为 \(B' \subseteq S'\) 意味着所有活动在 \(a_1\) 结束后才开始）

\(|B' \cup \{a_1\}| = |B'| + 1 > |A'| + 1 = |A|\)

矛盾！

贪心正确性证明

定理：贪心算法产生最大兼容子集

点击查看证明

设贪心选择的活动为 \(g_1, g_2, \ldots, g_k\)（按结束时间排序）

设最优解选择的活动为 \(o_1, o_2, \ldots, o_m\)（按结束时间排序）

引理（保持领先）：对所有 \(r \leq k\)，\(f(g_r) \leq f(o_r)\)

归纳证明：

基础情况 \(r = 1\)：贪心选择结束时间最早的活动，\(f(g_1) \leq f(o_1)\)

归纳步 \(r - 1 \to r\)：假设 \(f(g_{r-1}) \leq f(o_{r-1})\)

由于 \(o_r\) 与 \(o_{r-1}\) 兼容：\(s(o_r) \geq f(o_{r-1}) \geq f(g_{r-1})\)

因此 \(o_r\) 也在 \(g_{r-1}\) 结束后，是贪心在第 \(r\) 步的候选

所以 \(f(g_r) \leq f(o_r)\)

结论：假设 \(m > k\)

则 \(f(g_k) \leq f(o_k) \leq s(o_{k+1})\)，活动 \(o_{k+1}\) 在 \(g_k\) 结束后才开始，与 \(g_k\) 兼容

但贪心在 \(g_k\) 后没有选择更多活动，矛盾

因此 \(k \geq m\)

递归版本

CLRS 中的递归贪心（更直接展示贪心选择 + 子问题递归）：

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n):
    // 找在 aₖ 之后开始的最早结束活动
    m ← k + 1
    while m ≤ n and s_m < f_k:
        m ← m + 1
    if m ≤ n:
        return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
    else:
        return ∅

初始调用 RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)（\(a_0\) 是虚拟活动，\(f_0 = 0\)）

---

区间划分/着色

\(n\) 个讲座，讲座 \(j\) 占用时间 \([s_j, f_j)\)

目标：将讲座分配到最少数量的教室，且每个教室中的讲座互不冲突

结构下界

定义：深度 (depth) = 在任一时间点同时进行的最大讲座数

深度是教室数的下界：同一时刻进行的讲座必须分配到不同教室

贪心算法

INTERVAL-PARTITION(L):
    按开始时间排序使 s₁ ≤ s₂ ≤ ... ≤ sₙ
    d ← 0
    for j = 1 to n:
        if 存在教室 k 使得其最后一个讲座在 sⱼ 前结束:
            将讲座 j 分配到教室 k
            更新教室 k 的最后结束时间为 fⱼ
        else:
            d ← d + 1
            将讲座 j 分配到新教室 d
    return d

实现：用最小堆维护每个教室的最后结束时间

• 判断兼容性：比较 \(s_j\) 与堆顶（最早结束的教室）
• 分配讲座：EXTRACT-MIN 后 INSERT 更新后的结束时间
• 新开教室： INSERT

\(O(n)\) 次堆操作，每次 \(O(\log n)\)，加上排序，总时间 \(O(n \log n)\)

例子：

• A：[0, 10)
• B：[5, 15)
• C：[10,15)
• D：[12, 20)
• E：[15, 25)

接着分配：对 A，分到教室1，教室1 结束时间更新为 10

对 B，教室1 结束时间 10 > B 开始时间 5，不可分配；分到教室2，教室2 结束时间更新为 15

对 C，教室1 结束时间 10 ≤ C 开始时间 10，可分配；教室2 结束时间 15 > C 开始时间 10，不可分配；分到教室1，教室1 结束时间更新为 15

对 D，教室1 结束时间 15 > D 开始时间 12，不可分配；教室2 结束时间 15 > D 开始时间 12，不可分配；分到教室3，教室3 结束时间更新为 20

对 E，教室1 结束时间 15 ≤ E 开始时间 15，可分配；教室2 结束时间 15 ≤ E 开始时间 15，可分配；教室3 结束时间 20 > E 开始时间 15，不可分配；分到教室1，教室1 结束时间更新为 25

一共使用了 3 个教室，深度也是 3（在时间点 12-15 同时进行 B、C、D）

正确性：保持领先

定理：贪心算法使用的教室数恰好等于深度

点击查看证明

设贪心分配了 \(d\) 个教室

只需证明 depth \(\geq d\)（因为 depth \(\leq d\) 是显然的——贪心不会用多余的教室）

对于讲座 \(j\)，此时时刻 \(s_j\)

当开第 \(d\) 个教室时，是因为讲座 \(j\) 与前 \(d-1\) 个教室都不兼容

即前 \(d-1\) 个教室各有一个讲座在时刻 \(s_j\) 之后才结束

由于按开始时间排序，这 \(d-1\) 个讲座的开始时间都 \(\leq s_j\)

因此在时刻 \(s_j + \varepsilon\)，有 \(d\) 个讲座同时进行（\(d-1\) 个未结束的 + 讲座 \(j\) 本身）\(\varepsilon > 0\)

depth \(\geq d\)

又因 depth 是下界：任何调度方案至少需要 depth 个教室

所以 depth \(= d\)，贪心最优

---

最小化延迟

\(n\) 个工作，工作 \(j\) 需要 \(t_j\) 时间处理，截止时间为 \(d_j\)

单台机器，一次只能处理一个工作，工作 \(j\) 在时间 \(f_j\) 完成时延迟 \(l_j = \max(0, f_j - d_j)\)

目标：最小化最大延迟 \(L_{\max} = \max_j l_j\)

贪心策略的选择

策略	描述	最优？	反例
最短处理时间	按 \(t_j\) 升序	否	\(t_1=1, d_1=100\) 和 \(t_2=10, d_2=10\)
最小松弛度	按 \(d_j - t_j\) 升序	否	\(t_1=1, d_1=2\) 和 \(t_2=10, d_2=10\)
最早截止时间	按 \(d_j\) 升序	是	—

最早截止时间 (EDD) 算法

EARLIEST-DEADLINE-FIRST:
    按截止时间排序使 d₁ ≤ d₂ ≤ ... ≤ dₙ
    t ← 0
    for j = 1 to n:
        将工作 j 分配到时间 [t, t + tⱼ]
        fⱼ ← t + tⱼ
        t ← t + tⱼ
    return 调度方案

正确性证明：交换论证

定义：调度中的逆序 (inversion) 是一对工作 \((i, j)\)，其中 \(d_i < d_j\) 但 \(j\) 排在 \(i\) 前面

容易得知 1：没有空闲时间的调度中，最大延迟只取决于工作的排列顺序

容易得知 2：贪心调度 \(S\) 没有逆序，也没有空闲时间

点击查看交换论证证明

定理：贪心调度 \(S\) 是最优的

证明：

设 \(S^*\) 是一个具有最少逆序的最优调度（若有多个，选逆序最少的）

情况 1：\(S^*\) 没有逆序

则 \(S^*\) 按截止时间排序，与 \(S\) 完成时间相同（可能不唯一但 \(L_{\max}\) 相同）

情况 2：\(S^*\) 有逆序

存在相邻逆序：两个相邻工作 \(i, j\)，\(j\) 紧接在 \(i\) 前面，但 \(d_j > d_i\)

（有逆序则必有相邻逆序——冒泡排序的原理）

设交换前 \(i\) 在 \([t, t+t_i]\) 完成，\(j\) 在 \([t+t_i, t+t_i+t_j]\) 完成

交换后 \(j\) 在 \([t, t+t_j]\) 完成，\(i\) 在 \([t+t_j, t+t_j+t_i]\) 完成

逆序 \((i, j)\)：\(i\) 排在 \(j\) 前面，但 \(d_i > d_j\)

交换前，\(t_0\) 时刻开始工作 \(i\)，延迟 \(l_0 = t_0 + t_i - d_i\)

\(t_0 + t_i\) 时刻开始工作 \(j\)，延迟 \(l_1 = t_0 + t_i + t_j - d_j\)

交换后，\(t_0\) 时刻开始工作 \(j\)，延迟 \(l_0' = t_0 + t_j - d_j\)

\(t_0 + t_j\) 时刻开始工作 \(i\)，延迟 \(l_1' = t_0 + t_j + t_i - d_i\)

由于 \(d_j > d_i\)，则 \(l_1' > l_1\)

显然 \(l_1' > l_0\)，所以 \(\max(l_0', l_1') = l_1' > \max(l_0, l_1) = L_{\max}^{\text{old}}\)

交换后逆序数减少了 1，\(S^*\) 是最优的，所以 \(L_{\max}^{\text{new}} \geq L_{\max}^{\text{old}}\)

不断交换得到一个没有逆序的调度 \(S'\)，\(L_{\max}^{S'} \geq L_{\max}^{S^*}\)

也就是贪心调度

---

Huffman 编码

问题定义 (CLRS 16.3)

字符集 \(C\)，每个字符 \(c\) 有频率 \(f(c)\)

目标：构造二进制前缀码，最小化平均编码长度（即编码文件的总位数）：

\[ B(T) = \sum_{c \in C} f(c) \cdot d_T(c) \]

\(d_T(c)\) 是字符 \(c\) 在编码树 \(T\) 中的深度

前缀码

前缀码 (prefix-free code)：没有任何字符的编码是另一字符编码的前缀

可用满二叉树表示：字符是叶节点，左分支 0 右分支 1

前缀码允许无歧义解码：从根沿树走到叶，输出字符，重复

引理 (CLRS)：最优前缀码对应满二叉树

证明：若内部节点只有一个子节点，去掉该节点，子节点上移，所有后代深度减 1，代价严格减小

CLRS 示例

字符	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)
频率(千)	45	13	12	16	9	5
定长编码	000	001	010	011	100	101
变长编码	0	101	100	111	1101	1100

定长：\(300 \times 3 = 300\)（千位）

变长：\(45 \times 1 + 13 \times 3 + 12 \times 3 + 16 \times 3 + 9 \times 4 + 5 \times 4 = 224\)（千位），节省 \(25\%\)

Huffman 算法

HUFFMAN(C):
    n ← |C|
    Q ← C                           // 最小堆，按频率
    for i ← 1 to n - 1:
        allocate 新节点 z
        z.left ← x ← EXTRACT-MIN(Q)
        z.right ← y ← EXTRACT-MIN(Q)
        z.freq ← x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT-MIN(Q)            // 返回树根

构造过程详细示例

初始堆: f:5, e:9, c:12, b:13, d:16, a:45

第 1 步: 取出 f(5), e(9), 合并为 z₁(14)
堆: c:12, b:13, z₁:14, d:16, a:45

第 2 步: 取出 c(12), b(13), 合并为 z₂(25)
堆: z₁:14, d:16, z₂:25, a:45

第 3 步: 取出 z₁(14), d(16), 合并为 z₃(30)
堆: z₂:25, z₃:30, a:45

第 4 步: 取出 z₂(25), z₃(30), 合并为 z₄(55)
堆: a:45, z₄:55

第 5 步: 取出 a(45), z₄(55), 合并为根(100)

   (100)
  /     \
a:45   (55)
       /    \
    (25)    (30)
    / \     /   \
  c:12 b:13 (14) d:16
            / \
          f:5 e:9

编码：\(a\): 0, \(c\): 100, \(b\): 101, \(f\): 1100, \(e\): 1101, \(d\): 111

\(B(T) = 45 \cdot 1 + 12 \cdot 3 + 13 \cdot 3 + 5 \cdot 4 + 9 \cdot 4 + 16 \cdot 3 = 224\)

时间：\(O(n \log n)\)（\(n-1\) 次 EXTRACT-MIN 和 INSERT，每次 \(O(\log n)\)）

正确性证明 (CLRS Theorem 16.3, 16.4)

点击查看贪心选择性质证明

引理 16.2：设 \(C\) 是字符集，\(f(c)\) 为频率。设 \(x, y\) 是频率最低的两个字符。则存在最优前缀码使 \(x, y\) 为兄弟（深度最大的两个叶子，编码仅最后一位不同）

证明：

设 \(T\) 是 \(C\) 的最优编码树。设 \(a, b\) 是 \(T\) 中深度最大的兄弟叶子（满二叉树最深层一定有兄弟）

不失一般性设 \(f(a) \leq f(b)\)，\(f(x) \leq f(y)\)

由 \(x, y\) 频率最低：\(f(x) \leq f(a)\)，\(f(y) \leq f(b)\)

交换 \(a\) 和 \(x\)（若 \(a \neq x\)）得到 \(T'\)：

\[B(T') - B(T) = f(x) \cdot d_{T'}(x) + f(a) \cdot d_{T'}(a) - f(x) \cdot d_T(x) - f(a) \cdot d_T(a)\]

交换后 \(d_{T'}(x) = d_T(a)\)，\(d_{T'}(a) = d_T(x)\)

\[= (f(x) - f(a))(d_T(a) - d_T(x))\]

\(f(x) - f(a) \leq 0\)，\(d_T(a) - d_T(x) \geq 0\)（\(a\) 在最深处）

所以 \(B(T') \leq B(T)\)，\(T'\) 也是最优的

同理交换 \(b\) 和 \(y\)（若 \(b \neq y\)），得到 \(x, y\) 为兄弟的最优树

点击查看最优子结构证明

引理 16.3：设 \(T\) 是 \(C\) 的最优编码树，\(x, y\) 是兄弟叶子，\(z\) 是它们的父节点。定义 \(C' = C \setminus \{x, y\} \cup \{z\}\)，其中 \(f(z) = f(x) + f(y)\)

设 \(T'\) 是将 \(T\) 中 \(x, y\) 去掉后得到的树（\(z\) 变为叶节点）

则 \(T'\) 是 \(C'\) 的最优编码树

证明：

\[d_T(x) = d_T(y) = d_{T'}(z) + 1\]

\[B(T) = B(T') + f(x) \cdot d_T(x) + f(y) \cdot d_T(y) - f(z) \cdot d_{T'}(z)\]

\[= B(T') + (f(x) + f(y))(d_{T'}(z) + 1) - (f(x) + f(y)) \cdot d_{T'}(z)\]

\[= B(T') + f(x) + f(y)\]

因此 \(B(T) = B(T') + f(x) + f(y)\)

反证：若 \(T'\) 不是 \(C'\) 的最优树，存在 \(T''\) 使 \(B(T'') < B(T')\)

在 \(T''\) 中将叶子 \(z\) 展开为 \(x, y\)，得到 \(C\) 的编码树 \(T'''\)

\(B(T''') = B(T'') + f(x) + f(y) < B(T') + f(x) + f(y) = B(T)\)

与 \(T\) 的最优性矛盾

点击查看 Huffman 算法正确性（综合）

定理 16.4：HUFFMAN 算法产生最优前缀码

证明（对 \(|C|\) 归纳）：

基础：\(|C| = 1\)，只有一个字符，编码为空串（或 0），显然最优

归纳步：假设 HUFFMAN 对 \(|C| - 1\) 个字符正确

算法选择频率最低的 \(x, y\)，合并为 \(z\)

由引理 16.2（贪心选择）：存在最优树使 \(x, y\) 为兄弟

由归纳假设：HUFFMAN 对 \(C' = C \setminus \{x, y\} \cup \{z\}\) 产生最优树 \(T'\)

由引理 16.3（最优子结构）：将 \(T'\) 中 \(z\) 展开为 \(x, y\) 得到 \(C\) 的最优树

Kraft 不等式

Kraft 不等式：存在码长为 \(l_1, l_2, \ldots, l_n\) 的前缀码，当且仅当

\[ \sum_{i=1}^{n} 2^{-l_i} \leq 1 \]

等号成立时对应满二叉树

Shannon 熵与编码效率

设 \(H = -\sum_{i} p_i \log_2 p_i\) 是 Shannon 熵（\(p_i = f_i / \sum f_j\)）

\[ H \leq L_{\text{Huffman}} < H + 1 \]

当且仅当所有频率都是 2 的幂时 \(L = H\)

Huffman 编码的实际应用

• DEFLATE 算法（gzip, zlib, PNG）：LZ77 + Huffman
• JPEG：DCT 变换后对系数 Huffman 编码
• MP3：MDCT + 心理声学模型 + Huffman

算术编码 vs Huffman：

• 算术编码更接近熵极限（平均码长可以小于 \(H + 1\)）
• 但 Huffman 实现更简单，解码更快
• 现代标准（H.265, JPEG XL）常用算术编码

---

分数背包

\(n\) 个物品，物品 \(i\) 有收益 \(b_i\) 和重量 \(w_i\)，背包容量 \(W\)

允许取物品的一部分，目标：最大化总收益

贪心算法

按价值密度 \(v_i = b_i / w_i\) 降序排列，依次尽量多取

FRACTIONAL-KNAPSACK(S, W):
    按 bᵢ/wᵢ 降序排序
    remaining ← W
    for i ← 1 to n:
        xᵢ ← min(wᵢ, remaining)
        remaining ← remaining - xᵢ
        if remaining = 0: break
    return Σ bᵢ · xᵢ/wᵢ

时间 \(O(n \log n)\)

正确性 (CLRS 16.2)

点击查看证明

定理：贪心算法对分数背包问题是最优的

反证：设贪心解为 \((x_1, \ldots, x_n)\)，存在更优解 \((y_1, \ldots, y_n)\)

由于两个解不同，存在物品 \(i, j\) 使得 \(x_i < y_i\)（贪心少取的）和 \(x_j > y_j\)（贪心多取的）

但贪心按价值密度排序，先尽量取密度高的。若 \(i\) 排在 \(j\) 前面（\(v_i \geq v_j\)），贪心应已最大化 \(x_i\)

因此必有 \(v_i \leq v_j\)。将 \(\delta = \min(x_i - y_i, y_j - x_j) > 0\) 单位的物品 \(j\) 替换为物品 \(i\)：

收益变化：\(\delta \cdot v_i - \delta \cdot v_j \leq 0\)

但这说明替换不会变好——矛盾于假设更优解存在

（更精确地：贪心总是先取密度最高的直到取完或容量满，所以不可能有更优的取法）

0-1 背包不能贪心

反例 (CLRS)：\(A\)(10kg, $60), \(B\)(20kg, $100), \(C\)(30kg, $120), \(W = 50\)

	价值密度	贪心选择	最优选择
\(A\)	6	全部	不选
\(B\)	5	全部	全部
\(C\)	4	不选	全部
总重		30kg	50kg
总价值		$160	$220

0-1 背包是 NP 难问题，需要 DP

---

拟阵与贪心 (CLRS 16.4)

拟阵的定义

拟阵 (Matroid)：\(M = (S, \mathcal{I})\)，\(S\) 为有限集，\(\mathcal{I} \subseteq 2^S\) 为独立集族，满足：

1. 遗传性：\(B \in \mathcal{I}\) 且 \(A \subseteq B\) 则 \(A \in \mathcal{I}\)
2. 交换性质：\(A, B \in \mathcal{I}\) 且 \(|A| < |B|\) 则 \(\exists x \in B \setminus A\) 使 \(A \cup \{x\} \in \mathcal{I}\)

\(\mathcal{I}\) 中的极大集称为基 (basis)，所有基大小相同

拟阵的例子

图拟阵：\(S = E\)（边集），\(A \in \mathcal{I}\) 当且仅当 \(A\) 无环（是森林）

基 = 生成树。这是 Kruskal 算法的理论基础

均匀拟阵：\(U_{k,n}\)，\(A \in \mathcal{I}\) 当且仅当 \(|A| \leq k\)

线性拟阵：向量集合中线性无关子集

加权拟阵上的贪心

给定拟阵 \(M = (S, \mathcal{I})\) 和权重函数 \(w: S \to \mathbb{R}_{> 0}\)

目标：找权重最大的独立集

GREEDY-ON-MATROID(M, w):
    按 w 降序排列 S 的元素
    A ← ∅
    for each x ∈ S（按权重递减）:
        if A ∪ {x} ∈ I:
            A ← A ∪ {x}
    return A

定理 (CLRS Theorem 16.11)：贪心算法在加权拟阵上产生最优解

点击查看证明

引理（贪心选择）：设 \(x\) 是 \(S\) 中权重最大的独立元素（\(\{x\} \in \mathcal{I}\)），则存在包含 \(x\) 的最优独立集

证明：设 \(B\) 是最优独立集，\(x \notin B\)。由交换性质，\(|{x}| < |B|\)（否则 \(B\) 也是大小 1 且权重最大含 \(x\)），存在 \(y \in B\) 使 ${x} … $ 这里需要更精细的论证

更精确地：设 \(B\) 是最优基，\(x \notin B\)。由交换性质（对 \(\{x\}\) 和 \(B\)），\(\{x\}\) 可以被扩展。但我们需要证 \(x\) 可以替换 \(B\) 中某元素

由拟阵理论（基交换引理）：存在 \(y \in B\) 使得 \((B \setminus \{y\}) \cup \{x\}\) 也是基

\(w((B \setminus \{y\}) \cup \{x\}) = w(B) - w(y) + w(x) \geq w(B)\)（因为 \(w(x) \geq w(y)\)，\(x\) 是最重独立元素）

因此替换后不比 \(B\) 差

引理（最优子结构）：选择 \(x\) 后，剩余问题在收缩拟阵 \(M / x\) 上仍可贪心求解

归纳即证

---

Dijkstra 算法

每步选择距离源点最近的未访问顶点，类似 Prim 选择连接树的最近顶点

DIJKSTRA(G, w, s):
    d[s] ← 0, d[v] ← ∞ 对所有 v ≠ s
    S ← ∅, Q ← V
    while Q ≠ ∅:
        u ← EXTRACT-MIN(Q)
        S ← S ∪ {u}
        for each v ∈ Adj[u]:
            if d[u] + w(u,v) < d[v]:
                d[v] ← d[u] + w(u,v)
                π[v] ← u

正确性（归纳 / 割论证）

点击查看证明

不变量：当 \(u\) 被提取时，\(d[u] = \delta(s, u)\)（真正最短距离）

归纳：假设之前提取的所有节点距离正确

设 \(u\) 是新提取的节点。假设 \(d[u] > \delta(s, u)\)

设 \(s \leadsto x \to y \leadsto u\) 是真正最短路径，\((x,y)\) 是第一条从 \(S\) 到 \(V \setminus S\) 的边

由归纳假设 \(d[x] = \delta(s, x)\)，松弛后 \(d[y] \leq d[x] + w(x,y) = \delta(s, y)\)

由非负权重：\(\delta(s, y) \leq \delta(s, u)\)

\(d[y] \leq \delta(s, y) \leq \delta(s, u) < d[u]\)

但 \(u\) 是从 \(Q\) 中提取的最小值，\(d[u] \leq d[y]\)，矛盾

前提条件：所有边权非负（\(w(u,v) \geq 0\)）。负权边时 Dijkstra 失效

Prim vs Dijkstra

	Prim	Dijkstra
key 含义	连接到树的最小边权	到源点的估计距离
更新规则	\(\text{key}[v] = w(u,v)\)	\(d[v] = d[u] + w(u,v)\)
求解问题	MST	最短路径
时间	\(O(E + V\log V)\)	\(O(E + V\log V)\)

---

交换论证的一般框架

通用交换论证模板

设贪心解为 \(G\)，最优解为 \(O^*\)

步骤 1（结构化最优解）：选择一个与贪心解”差异最小”的最优解 \(O^*\)

步骤 2（找到差异）：找到 \(G\) 和 \(O^*\) 的第一处不同

步骤 3（交换）：修改 \(O^*\)，使之更接近 \(G\)，但不变差

步骤 4（矛盾）：\(O^*\) 的差异减少，矛盾于”差异最小”

示例：活动选择的交换论证

贪心选 \(g_1, g_2, \ldots, g_k\)，最优选 \(o_1, o_2, \ldots, o_m\)

选差异最小的 \(O^*\)：设 \(r\) 是第一个使 \(g_r \neq o_r\) 的下标

交换 \(o_r\) 为 \(g_r\)：由保持领先，\(f(g_r) \leq f(o_r)\)，\(g_r\) 与 \(o_{r+1}, \ldots\) 不冲突

新的解 \(O^{**}\) 与 \(G\) 的差异比 \(O^*\) 少一个位置，矛盾

保持领先 vs 交换论证

保持领先 (Stay Ahead)：直接归纳证明贪心解在每一步都不比最优解差（适合活动选择、区间问题）

交换论证 (Exchange Argument)：通过局部修改将最优解变换为贪心解（适合调度、编码、排序相关问题）

两种方法本质等价，但在不同问题上各有方便之处

贪心算法设计步骤

1. 将问题转化为在每步做一个选择后剩下一个子问题的形式
2. 证明贪心选择性质：存在最优解包含贪心的第一个选择
3. 证明最优子结构：贪心选择后的子问题的最优解 + 贪心选择 = 原问题的最优解
4. 实现

贪心不适用的判断

反面信号：

• 需要回溯或尝试多种选择 → DP 或回溯
• 局部最优选择导致”锁死”（如 0-1 背包）
• 子问题之间不独立

附录

区间调度的对称性

选择最后开始的兼容活动（而非最早结束）也是最优的

证明：对时间轴取反（\(s'_i = -f_i\)，\(f'_i = -s_i\)），最早结束变为最后开始，正确性等价

0-1 背包的 DP 子结构

子问题：\(V(i, w)\) = 用物品 \(\{1, \ldots, i\}\)、容量 \(w\) 的最大价值

\[V(i, w) = \max(V(i-1, w), v_i + V(i-1, w - w_i))\]

时间 \(O(nW)\)（伪多项式）

用分数背包近似 0-1 背包

设 \(\text{OPT}_{0-1}\) 为 0-1 背包最优值，\(\text{OPT}_F\) 为分数背包最优值

引理：\(\text{OPT}_{0-1} \leq \text{OPT}_F\)

贪心按密度取完整物品直到装不下：设贪心值为 \(G\)，第一个装不下的物品价值为 \(v_k\)

\[G \geq \text{OPT}_F - v_k \geq \text{OPT}_{0-1} - \max_i v_i\]

若 \(\max_i v_i\) 远小于 \(\text{OPT}\)，则近似比接近 1

找零问题

面值 \(c_1 > c_2 > \cdots > c_k = 1\)，凑 \(n\) 分最少硬币数

标准面值（如 25, 10, 5, 1）：贪心最优

一般面值：贪心不一定最优。反例：\(\{1, 3, 4\}\) 凑 6，贪心 \(4+1+1=3\) 枚，最优 \(3+3=2\) 枚

DP：\(C[j] = \min_{c_i \leq j} \{C[j - c_i] + 1\}\)

定理（Magazine, Nemhauser, Trotter 1975）：对于面值为 \(\{1, c, c^2, \ldots, c^k\}\) 的货币系统（\(c \geq 2\)），贪心最优

最小化加权完成时间

\(n\) 个工作，权重 \(w_j\)，处理时间 \(p_j\)

目标：最小化 \(\sum_{j=1}^{n} w_j C_j\)（\(C_j\) 为完成时间）

Smith’s Rule (1956)：按 \(w_j / p_j\) 降序排列（WSPT 规则）

点击查看正确性证明

交换论证：设相邻工作 \(i, j\)，\(i\) 排在 \(j\) 前面

\(i\) 先做的代价：\(w_i(t + p_i) + w_j(t + p_i + p_j)\)

\(j\) 先做的代价：\(w_j(t + p_j) + w_i(t + p_j + p_i)\)

差值：\(w_i p_j - w_j p_i\)

\(i\) 先做更优当且仅当 \(w_i p_j \leq w_j p_i\)，即 \(w_i / p_i \geq w_j / p_j\)

因此按 \(w_j / p_j\) 降序排列使每对相邻工作的顺序最优

Huffman 编码的唯一性

Huffman 树的形状不唯一（同频率字符可以不同顺序合并，左右子树可交换），但所有 Huffman 编码的平均码长相同

调度理论拓展

多机调度的贪心近似

\(n\) 个工作，\(m\) 台相同机器，工作 \(j\) 处理时间 \(p_j\)，目标最小化 makespan（最后完成时间）

LPT (Longest Processing Time First) 规则：按处理时间降序分配

定理 (Graham, 1969)：LPT 是 \(\frac{4}{3} - \frac{1}{3m}\) 近似算法

点击查看证明思路

设 OPT 为最优 makespan。\(\text{OPT} \geq \max(\max_j p_j, \frac{1}{m}\sum_j p_j)\)

LPT 调度中，设最后完成的工作为 \(j\)，它开始时间为 \(s_j\)

\(s_j \leq \frac{1}{m}(\sum_k p_k - p_j)\)（因为 \(j\) 分配到负载最小的机器）

\(\text{LPT} = s_j + p_j \leq \frac{1}{m}\sum_k p_k - \frac{1}{m}p_j + p_j = \frac{1}{m}\sum_k p_k + (1 - \frac{1}{m})p_j\)

\(\leq \text{OPT} + (1 - \frac{1}{m})p_j\)

若 \(p_j \leq \text{OPT}/3\)（LPT 排序下，\(j\) 是最小的工作之一）：

\(\text{LPT} \leq \text{OPT} + \frac{1}{3}(1 - \frac{1}{m})\text{OPT} = (\frac{4}{3} - \frac{1}{3m})\text{OPT}\)

List Scheduling（按任意顺序分配到最空闲机器）：\(2 - \frac{1}{m}\) 近似

加权完成时间推广

单机带释放时间的加权完成时间最小化是 NP 难的

Smith’s Rule 的推广（WSPT with release dates）

经典贪心算法总结

问题	贪心策略	证明方法	时间
活动选择	最早结束	保持领先	\(O(n \log n)\)
区间划分	最早开始	结构下界	\(O(n \log n)\)
最小化 \(L_{\max}\)	最早截止 (EDD)	交换论证	\(O(n \log n)\)
最小化 \(\sum w_j C_j\)	WSPT	交换论证	\(O(n \log n)\)
Huffman 编码	最低频合并	贪心选择+子结构	\(O(n \log n)\)
分数背包	最大密度	交换论证	\(O(n \log n)\)
MST (Kruskal)	最小权边	割性质/拟阵	\(O(E \log E)\)
MST (Prim)	最近顶点	割性质	\(O(E + V\log V)\)
Dijkstra	最近未访	归纳	\(O(E + V\log V)\)

贪心 vs DP vs 分治

特征	贪心	DP	分治
子问题重叠	不关心	是（核心）	否
最优子结构	是	是	不必须
选择时机	子问题求解前	子问题求解后	递归分解
回溯	不回溯	考虑所有选择	合并子解