贪心算法：贪心选择性质、交换论证法与经典模型

2026年11月5日笔记算法 zh-CN

贪心算法（Greedy Algorithm）通过在一系列决策阶段中，每一步仅根据当前局部信息做出“在某种标准下当前最优”的选择，随后自顶向下地将原问题转化为规模更小的单向子问题。与动态规划在每阶段完备枚举所有分支不同，贪心算法通过依赖问题的特定代数结构提前确定决策分支，因而通常具有更高的时间与空间效率。

一、贪心算法理论基石与适用条件

应用贪心策略求解最优化问题，必须严格证明以下两大数学要素：

贪心选择性质（Greedy-choice Property）：
所求问题的全局最优解可以通过一系列局部的贪心选择来达到。也就是说：在所有可能构成的全局最优解集合中，至少存在一个最优解，它包含了算法当前所做出的局部贪心选择。
最优子结构性质（Optimal Substructure）：
做出贪心选择后，原问题化简为一个与原问题同构但规模更小的子问题，且原问题的最优解包含其子问题的最优解。

flowchart LR
    A["当前问题规模 n"] -->|执行局部贪心选择| B["单向确定分支 (不回溯)"]
    B --> C["剩余独立子问题 (规模更小)"]
    C -->|递归/迭代继续贪心| D["全局最优解"]

二、交换论证法（Exchange Argument）通用证明范式

证明贪心选择性质最严密、最通用的数学工具是交换论证法。其核心证明框架分为以下五个标准化步骤：

定义贪心选择：设算法依据贪心准则所选取的首个元素为 $g$ ；
引入假设最优解：假设存在任意一个全局最优解 $O$ 。若 $g \in O$ ，则说明该最优解已经自然包含了贪心选择，命题自明成立；
定位替换元素：若 $g \notin O$ ，则在解集合 $O$ 中定位一个与 $g$ 角色对立的元素 $o \in O$ （通常为 $O$ 中排序后首个未按贪心准则选取的元素）；
构造新解并验证：构造新解集合 $O' = (O \setminus \{o\}) \cup \{g\}$ $O^{'} = (O ∖ {o}) \cup {g}$ ，严密推导并证明两点：
- 可行性（Feasibility）：替换后的新解 $O'$ 依然严格满足原问题的所有物理或逻辑约束条件；
- 最优性（Optimality）：新解的目标函数值不劣于原最优解（即收益不减少，或代价不增加）： $f(O') \ge f(O)$ ；
结论归纳：由此确证 $O'$ 同样是全局最优解，且它包含局部贪心选择 $g$ 。剩余子问题按数学归纳法推演即可。

三、活动安排问题（Activity Selection）

问题描述：设有 $n$ 个活动集合 $S = \{1, 2, \dots, n\}$ ，活动 $i$ 占用时间区间 $[s_i, f_i)$ （ $s_i$ 为开始时间， $f_i$ 为结束时间）。所有活动共享同一个不可并发的会场。若两活动的区间无重叠（ $s_j \ge f_i$ 或 $s_i \ge f_j$ ），则称二者相容。目标是选择一个包含活动数量最多的互不冲突的相容活动子集。

贪心策略：将所有活动按结束时间 $f_i$ 升序排列，每次优先选取结束时间最早且与已选活动相容的活动。

3.1 交换论证法完整证明

设贪心解与最优解：设活动全集按结束时间升序排列： $f_1 \le f_2 \le \dots \le f_n$ 。贪心算法选取的首个活动即为 1（满足 $f_1 = \min_i f_i$ ）。设 $A$ 为该问题的一个最大相容活动集合（最优解），将 $A$ 中的活动同样按结束时间升序排列，设其首个活动为 $k$ 。
情形讨论：
- 若 $k = 1$ ，则最优解 $A$ 包含贪心选择 1，命题成立；
- 若 $k \ne 1$ ，由贪心选择可知 $f_1 \le f_k$ 。
构造替换：令 $A' = (A \setminus \{k\}) \cup \{1\}$ $A^{'} = (A ∖ {k}) \cup {1}$ 。
- 可行性检验：由于集合 $A$ 内所有活动互不冲突，故 $A$ 中排在 $k$ 之后的所有其余活动 $j \in A \setminus \{k\}$ ，其开始时间均满足 $s_j \ge f_k$ 。因为 $f_1 \le f_k$ ，必然传递导出 $s_j \ge f_1$ 。这表明活动 1 与 $A$ 中后续的所有活动均无时间冲突，集合 $A'$ 绝对合法相容；
- 最优性检验：显然集合元素基数 $|A'| = |A|$ ，即安排的活动总数并未减少， $A'$ 同样为最优解。
由此确证：至少存在一个全局最优解包含结束时间最早的活动 1。原问题成功归约为在区间 $[f_1, \infty)$ 内的子问题，由数学归纳法确证算法正确性。

3.2 常见错误贪心策略的反例剖析

策略：按开始时间最早贪心：
- 反例：活动 1 占用区间 $[0, 100)$ ，另有活动 2 占用 $[1, 2)$ ，活动 3 占用 $[2, 3)$ 。该策略将选取活动 1，仅能开办 1 场；而最优解选取活动 2 和 3，可开办 2 场。超长活动阻断了后续整个会场。
策略：按持续时间最短（ $f_i - s_i$ 最小）贪心：
- 反例：活动 1 占用 $[0, 4)$ ，活动 2 占用 $[4, 8)$ ，活动 3 占用 $[3, 5)$ 。活动 3 持续时间为 2（最短），若选活动 3，则活动 1 和 2 均发生冲突被排斥，最终仅得 1 场；最优解选取活动 1 和 2，可安排 2 场。

直观机理：尽早结束能最大程度保留剩余可用时间区间，为后续接纳更多活动留出最广阔的可行域。

3.3 变式对比：单会场活动安排 vs 最小会场数分配

单会场问题：目标是在一个会场内排最多活动 $\to$ 按结束时间升序贪心；
会场安排问题：目标是安排全部活动且使用的会场总数最少 $\to$ 按开始时间升序排列，利用小根堆维护各个会场当前的空闲时间；若当前活动开始时间晚于最早空出的会场，则复用该会场，否则新开辟会场。

四、连续背包与单船最优装载问题

4.1 分数背包（Fractional Knapsack）

问题：背包容量为 $C$ ，物品可按任意连续比例分割。物品 $i$ 价值为 $v_i$ ，重量为 $w_i$ 。

贪心策略：按单位重量价值（价值密度 $\rho_i = v_i / w_i$ ）降序排列，优先装入密度最高的物品；装不下的最后一件按剩余承重截取相应比例。

交换证明：若某可行解未填满高密度物品而容纳了低密度物品，将低密度部分替换为等重的高密度部分，总承重不变，总价值严格增加。因此密度贪心必能达到全局最优。
0-1 背包贪心失效的原因：由于 0-1 背包物品不可分割，按密度贪心可能导致无法填满背包，剩余的碎片容量无法被利用，从而产生次优解（例如容量 50，物品 $(w,v)$ : (10,60), (20,100), (30,120)；密度贪心得 160，最优解选后两者得 220）。

4.2 单船最优装载问题

问题：载重上限为 $C$ ，有 $n$ 个集装箱，第 $i$ 个重量为 $w_i$ 。目标是装入尽可能多的集装箱件数（每件物品的价值均记为 1）。

贪心策略：按重量升序排列，优先装载最轻的集装箱直至超重。

交换论证：设最优解 $A$ 未选当前最轻集装箱 $g$ （ $w_g \le w_k$ ），而包含较重集装箱 $k$ 。令 $A' = (A \setminus \{k\}) \cup \{g\}$ ，总重量减少 $w_k - w_g \ge 0$ ，船体依然安全且装载件数保持不变。

五、哈夫曼编码（Huffman Coding）与最优前缀码

前缀码（Prefix Code）要求任意字符的编码均不能是其他字符编码的前缀，其天然对应一棵叶子节点为字符的二叉树。设字符 $x_i$ 的出现频率为 $w_i$ ，在树中的叶子深度（码长）为 $\ell_i$ 。优化目标是最小化加权路径长度（WPL）：

\mathrm{WPL} = \sum_{i=1}^n w_i \cdot \ell_i.

5.1 贪心算法执行机制

将每个字符构造成单节点二叉树，节点权值为字符频数，构建小根堆；
每次从小根堆中弹出权值最小的两个节点 $x, y$ ；
创建新父节点 $z$ ，令 $z$ 的左右孩子分别为 $x$ 和 $y$ ，其权值为 $w(z) = w(x) + w(y)$ ；
将新节点 $z$ 重新插回小根堆中；
重复步骤 2—4，共执行 $n-1$ 次合并，直至堆中仅剩单个根节点。

flowchart TD
    H["优先队列 (小根堆)"] -->|弹出权值最小两项| N1["节点 x (权值 a)"]
    H -->|弹出权值最小两项| N2["节点 y (权值 b)"]
    N1 --> P["新建父节点 z (权值 a + b)"]
    N2 --> P
    P -->|插回小根堆| H

5.2 贪心正确性核心证明要点

贪心选择性质：设 $x, y$ $x, y$ 为字符集中出现频数最低的两个字符。必存在一棵最优二叉前缀树，使得 $x$ $x$ 和 $y$ $y$ 在树中处于最深层次且互为兄弟节点。
- 证明：设最优树中深度最深的两个兄弟叶子为 $a, b$ 。由于 $w(x), w(y)$ 是全集频数极小值，显然 $w(x) \le w(a)$ 且 $w(y) \le w(b)$ 。若将 $x$ 与 $a$ 对换、 $y$ 与 $b$ 对换，由代数推导可知 $\Delta \mathrm{WPL} \le 0$ ，树的总代价不增加，故贪心合并必定包含在某个最优树中。
最优子结构性质：将两节点合并为单节点 $z$ 后，新树的 WPL 严格满足：
$\mathrm{WPL}(T) = \mathrm{WPL}(T') + w(x) + w(y).$
子树的优化直接导出原树的全局优化。

六、图论经典贪心算法

6.1 单源最短路径：Dijkstra 算法与非负权边先决条件

设源点为 $s$ 。维护已确定最短路径的顶点集合 $S$ 。定义 dist[v] 为当前从源点 $s$ 出发、仅经过 $S$ 中的中间节点到达 $v$ 的最短估计距离。

贪心选择：每一步从未确定集合 $V \setminus S$ 中选取 dist[u] 最小的顶点 $u$ ，将其加入 $S$ 并定案；
松弛操作（Relaxation）：遍历 $u$ 的所有出边 $(u, v)$ ，尝试更新：
$\mathrm{dist}[v] \leftarrow \min\big(\mathrm{dist}[v],\ \mathrm{dist}[u] + w(u, v)\big).$

[!CAUTION]
非负权边的先决条件与反例：
Dijkstra 算法成立的前提为：图中所有边的权值必须非负（ $w \ge 0$ ）。

证明依据：因为边权非负，路径长度随节点增加单调不减。在集合 $V \setminus S$ 中拥有最小 dist[u] 的顶点 $u$ ，若从源点先绕经其他未确定顶点 $x$ 再到达 $u$ ，路径全长必为 $\mathrm{dist}[x] + \dots \ge \mathrm{dist}[u] + \dots \ge \mathrm{dist}[u]$ ，绝不可能出现比当前值更短的路径，因此 $u$ 可以安全定案；

负权边破坏性反例：设有向图 $s \to a = 2$ ， $s \to b = 5$ ， $b \to a = -4$ 。算法首先选出 dist[a] = 2 并将其加入 $S$ 定案；然而真实最短路为 $s \to b \to a = 5 + (-4) = 1$ 。Dijkstra 的贪心单向定案彻底失效。

6.2 最小生成树（MST）：割性质与 Prim/Kruskal 算法

在连通无向图 $G=(V, E)$ 中，最小生成树是覆盖所有顶点的无环连通子图，且边权和达到最小。

割性质（Cut Property）：
设连通图的一个割 $(S, V \setminus S)$ 将顶点集切为两部分。若边 $e = (u, v)$ 是横跨该割的所有交叉边中权值最小的一条轻量边（Light Edge），则图 $G$ 的某棵最小生成树中必包含边 $e$ 。

证明：设最小生成树 $T$ 未包含边 $e$ 。将 $e$ 加入 $T$ 必然形成一个简单回路，该回路至少包含另一条横跨该割的边 $e'$ 。由于 $e$ 是轻量边， $w(e) \le w(e')$ 。构造新树 $T' = T \cup \{e\} \setminus \{e'\}$ ， $T'$ 依然保持连通无环，且 $w(T') = w(T) + w(e) - w(e') \le w(T)$ ，故 $T'$ 同样为最小生成树。

比较维度	Prim 算法	Kruskal 算法
贪心推进视角	以顶点集合为中心（树向外延伸生长）	以全图边集合为中心（全局升序选边）
局部贪心准则	选取连接已生成树与树外顶点的最轻量跨割边	选取全图剩余边中权值最小且不形成回路的边
防环路机制	目标端点天然处于树外，绝对无环	采用并查集（Disjoint Set）高效检测连通分量
时间复杂度	二叉堆实现： $O((V+E)\log V)$	边排序主导： $O(E\log E) = O(E\log V)$
适用图类型	稠密图（Dense Graphs， $E \approx V^2$ ）	稀疏图（Sparse Graphs， $E \ll V^2$ ）

七、多机调度问题与近似算法（LPT 规则）

问题：将 $n$ 个独立作业分配到 $m$ 台相同的机器上加工。作业不可抢占，目标是最小化最终完工时间（Makespan）。该问题在理论上被严格证明为 NP 完全问题。

LPT 启发式贪心策略（Longest Processing Time First）：

将所有作业按加工时间 $t_i$ 单调降序排列；
依次将当前作业分配给当前累计负载最小的机器。

该策略不能保证在所有输入下均获得绝对最优解，属于近似算法。Graham 定理证明其近似比满足：

\frac{T_{\mathrm{LPT}}}{T_{\mathrm{OPT}}} \le \frac{4}{3} - \frac{1}{3m}.

反例：设 2 台机器，作业集为 $\{3, 3, 2, 2, 2\}$ 。

LPT 分配结果：机器 1 分配 $\{3, 2, 2\}$ （总耗时 7），机器 2 分配 $\{3, 2\}$ （总耗时 5），最大完工时间为 7；
全局最优解：机器 1 分配 $\{3, 3\}$ （总耗时 6），机器 2 分配 $\{2, 2, 2\}$ （总耗时 6），最大完工时间仅为 6。