量化交易中文教材

第 16 章 贪心算法

贪心算法每一步都做"当前看来最好"的选择，并且不回头。它比动态规划简单、快得多，但并不总是对的。本章的重点不是背几个贪心算法，而是学会判断：什么时候局部最优能拼成全局最优（贪心选择性质 + 最优子结构，以及更一般的拟阵理论），什么时候不能（0-1 背包、整手约束、带权区间）。这个判断在量化里随处可用：按信号强度从高到低选股什么时候是最优的？加了资金或整手约束之后为什么就不是了？

学习目标

  1. 通过活动选择问题理解贪心与动态规划的关系：从 DP 的递归式出发，发现只需考虑一种选择。
  2. 掌握证明贪心算法正确的两个要素——贪心选择性质（交换论证）与最优子结构。
  3. 能用分数背包与 0-1 背包的对比，判断贪心何时失效、何时需要动态规划。
  4. 掌握 Huffman 编码的算法与最优性证明，并能估计行情数据的压缩率。
  5. 理解拟阵的定义与"加权拟阵上贪心必最优"的定理，能识别常见的拟阵约束（均匀拟阵、划分拟阵、图拟阵、任务调度）。
  6. 能在选股、事件交易调度、数据缓存等场景中正确选用贪心或 DP。

读前导读

这一章在解决什么问题。 贪心就是"每一步拿眼前最好的，拿了不退"。投资里最常见的贪心是：把股票按 alpha 从高到低排，挑前 \(K\) 只。问题是这个做法什么时候真的最优？如果只是"最多选 \(K\) 只"，它是最优的；如果加上"每个行业最多 1 只"，它仍然是最优的；但一旦加上"总资金不超过 20 万、按整手买"，它就可能错得很离谱（本章实战里只拿到最优值的 64%）。本章就是要给你一把尺子，判断手头的约束属于"贪心够用"的那一类，还是"必须做全局优化"的那一类。

上一章的动态规划会把所有选择都试一遍再比较；贪心只试一种。所以贪心快，但需要证明"只试这一种不会错过最优解"。本章的证明几乎都用同一个套路——交换论证：拿一个假想的最优解，把它的某个选择换成贪心的选择，证明结果不会变差。这个套路你在财务里其实用过：证明"组合里某资产权重偏离最优时，把一点权重从边际效用低的资产挪到高的资产能改进"。

需要先想起来的数学。

  • 集合记号。 \(A\subseteq B\)：\(A\) 是 \(B\) 的子集（\(A\) 里的东西 \(B\) 里都有）；\(B-A\)：在 \(B\) 里但不在 \(A\) 里的元素；\(A\cup\{x\}\)：往 \(A\) 里加一个元素 \(x\)；\(|A|\)：\(A\) 里元素的个数；\(\emptyset\)：空集。例：\(A=\{1,2\}\)，\(B=\{1,2,5\}\)，则 \(A\subseteq B\)，\(B-A=\{5\}\)，\(|B|=3\)。见 第 00 册第 08 章 读懂数学证明与符号。
  • 对数 \(\lg\) 与 \(\log_2\)。 本书 \(\lg n=\log_2 n\)。\(n\) 个不同符号用定长二进制编码至少要 \(\lceil\lg n\rceil\) 位（\(\lceil\cdot\rceil\) 是向上取整）：21 种取值需要 5 位，因为 \(2^4=16<21\le32=2^5\)。见 第 00 册第 04 章 级数与收敛。
  • 证明的读法：反证与"存在一个最优解包含……"。 贪心的正确性定理通常不说"贪心的解就是那个唯一最优解"，而说"存在一个最优解包含贪心的第一步"。最优解可以不唯一，只要贪心的选择不把我们排除在所有最优解之外就够了。见第 08 章同一册。
  • 复杂度记号 \(O\)、\(\Theta\)。 \(\Theta(n)\) 表示上下界都与 \(n\) 同阶，\(O(n\lg n)\) 是排序的典型代价。见 第 00 册第 07 章 概率中的分析工具 的大 O 部分。

怎么读这一章。 16.1 和 16.2 是核心：活动选择的交换论证要读懂，分数背包与 0-1 背包的对比要能用自己的话讲出来——这是全章最有用的判断。16.3 Huffman 编码可以先看算法和例子，两条引理的证明第一次只看思路。16.4、16.5 拟阵标了"选读"，但如果你做组合构建，建议至少读懂 16.4.1 的三条定义和 16.4.2 的结论"约束是拟阵 → 按权重从大到小能选就选必定最优"，并直接跳到 16.7.2 看选股的例子。16.6 思考题速览可以略读。

16.1 活动选择问题

16.1.1 问题

\(n\) 个活动 \(S=\{a_1,\dots,a_n\}\) 竞争同一个资源（比如一个阶梯教室），同一时刻只能有一个活动使用。活动 \(a_i\) 占用半开区间 \([s_i,f_i)\)。若两个区间不重叠（\(s_i\ge f_j\) 或 \(s_j\ge f_i\)），称它们兼容（compatible）。活动选择问题：选出规模最大的互相兼容的活动子集。假设活动已按结束时间排序：\(f_1\le f_2\le\cdots\le f_n\)。

原书例：

\(i\) 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 9 9 10 11 12 14 16

\(\{a_3,a_9,a_{11}\}\) 兼容但不是最大的；\(\{a_1,a_4,a_8,a_{11}\}\) 和 \(\{a_2,a_4,a_9,a_{11}\}\) 都是最大兼容子集。

16.1.2 先看动态规划

令 \(S_{ij}\) 为在 \(a_i\) 结束之后开始、在 \(a_j\) 开始之前结束的活动集合，\(A_{ij}\) 为它的一个最大兼容子集。若 \(A_{ij}\) 包含 \(a_k\)，则剩下两个子问题 \(S_{ik}\) 与 \(S_{kj}\)，且 \(A_{ij}\cap S_{ik}\)、\(A_{ij}\cap S_{kj}\) 必须分别是它们的最优解（剪切—粘贴）。于是

\[c[i,j]=\begin{cases}0 & S_{ij}=\emptyset,\\ \max_{a_k\in S_{ij}}\{c[i,k]+c[k,j]+1\} & S_{ij}\ne\emptyset.\end{cases}\]
这能得到一个 \(O(n^3)\) 的 DP（习题 16.1-1）。但它忽略了这个问题的一个关键性质。

16.1.3 贪心选择

直觉：应该选一个让资源尽量多地留给其他活动的活动——最早结束的那个。由于已经按结束时间排好序，贪心选择就是 \(a_1\)。选了它之后只剩一个子问题：在 \(a_1\) 结束后开始的活动 \(S_1\)（不可能有活动在 \(a_1\) 开始之前结束，因为 \(f_1\) 是最早的结束时间）。

定理 16.1：对任意非空子问题 \(S_k\)，设 \(a_m\) 是其中结束最早的活动，则 \(a_m\) 属于 \(S_k\) 的某个最大兼容子集。

证明（交换论证, exchange argument）. 取 \(S_k\) 的任一最大兼容子集 \(A_k\)，设 \(a_j\) 是其中最早结束的。若 \(a_j=a_m\) 则得证。否则令 \(A_k'=A_k-\{a_j\}\cup\{a_m\}\)。因为 \(f_m\le f_j\)，而 \(A_k\) 中其他活动都在 \(f_j\) 之后开始，所以 \(A_k'\) 中的活动仍两两兼容，且 \(|A_k'|=|A_k|\)，它也是最大兼容子集并包含 \(a_m\)。\(\square\)

推导拆解：用原书例子走一遍。最早结束的是 \(a_1=[1,4)\)。假设有人拿出最优解 \(\{a_2,a_4,a_9,a_{11}\}\)，它最早结束的是 \(a_2=[3,5)\)，不是 \(a_1\)。把 \(a_2\) 换成 \(a_1\)：\(a_1\) 在 4 结束，比 \(a_2\) 的 5 更早；而 \(a_4,a_9,a_{11}\) 都在 5 之后（因此也在 4 之后）开始，所以换完仍互不冲突，个数还是 4 个。于是"存在一个包含 \(a_1\) 的最优解"成立。 证明里每一步用到的事实：(1) \(f_m\le f_j\) 来自"\(a_m\) 是 \(S_k\) 中最早结束的"；(2) "其他活动都在 \(f_j\) 之后开始"来自 \(A_k\) 两两兼容且 \(a_j\) 是其中最早结束的；(3) 两者合起来，换进来的 \(a_m\) 不会和任何其他活动冲突。末尾的 \(\square\) 表示证明结束。 金融直觉：把一天当成一个交易通道，每个机会占用一段时间。"最早结束优先"就是"尽快把通道腾出来"，腾得越早，后面能接的机会越多。注意它只对"最多做几笔"最优，下面加权区间调度会说明，当每笔价值不同时这条规则就不成立了。

于是不必求解所有子问题：反复选最早结束且与已选活动兼容的活动即可。贪心算法通常是自顶向下的——先做选择，再解剩下的子问题；而 DP 是先解子问题，再做选择。

def GREEDY_ACTIVITY_SELECTOR(s, f):       # 活动已按 f 排序
    n = len(s)
    A = [1]; k = 1                        # k：最近加入 A 的活动
    for m in range(2, n + 1):
        if s[m] >= f[k]:                  # 与 A 中所有活动兼容
            A.append(m); k = m
    return A

由于按结束时间递增考察，\(f_k\) 总是 \(A\) 中所有活动的最大结束时间，所以只需检查 \(s_m\ge f_k\)。已排序时 \(\Theta(n)\)，否则排序 \(O(n\lg n)\)。原书例中依次选出 \(a_1,a_4,a_8,a_{11}\)。原书也给出了等价的递归版本，它几乎是尾递归的，可以直接改写成迭代。

"选最早结束的"不是唯一的贪心思路，但其他直观想法——选持续时间最短的、选与其他活动重叠最少的、选最早开始的——都有反例（习题 16.1-3）。另外两个变体在量化中常见：

  • 区间图着色（习题 16.1-4）：用最少的教室安排所有活动。按开始时间扫描，用优先队列维护各教室的空闲时刻，每来一个活动就复用最早空出的教室。所需教室数等于任一时刻重叠活动数的最大值（参见本册第 14 章思考题 14-1 的最大重叠点）。
  • 加权区间调度（习题 16.1-5）：每个活动有价值 \(v_i\)，求兼容子集的最大总价值。这时贪心失效，需要 DP：按结束时间排序后，\(OPT(j)=\max\big(OPT(j-1),\ v_j+OPT(p(j))\big)\)，\(p(j)\) 是结束时间不晚于 \(s_j\) 的最后一个活动，用二分查找求，共 \(O(n\lg n)\)。

16.2 贪心策略的要素

16.2.1 设计步骤

16.1 节先写 DP 再发现贪心，过程比通常繁琐。更直接的设计步骤是：

  1. 把最优化问题转化为"做出一个选择后只剩一个子问题"的形式；
  2. 证明原问题总存在一个包含贪心选择的最优解，即贪心选择是安全的；
  3. 证明最优子结构：贪心选择与剩下子问题的最优解合在一起，就是原问题的最优解。

每个贪心算法背后几乎都有一个更繁琐的 DP。

16.2.2 两个要素

贪心选择性质（greedy-choice property）：可以通过局部最优选择构造全局最优解。贪心的选择可以依赖之前做过的选择，但不能依赖将来的选择或子问题的解。证明通常用交换论证：取一个全局最优解，把其中某个选择换成贪心选择，说明结果仍然最优。贪心选择常可借助预处理（排序）或合适的数据结构（优先队列）快速做出。

最优子结构：做出贪心选择后，子问题的最优解与这个选择合起来就是原问题的最优解。这隐含地对子问题做了归纳。

16.2.3 分数背包与 0-1 背包

两种背包问题都有最优子结构，却一个能贪心、一个不能，是区分二者的标准例子。

  • 0-1 背包：\(n\) 件商品，第 \(i\) 件价值 \(v_i\)、重 \(w_i\)，背包容量 \(W\)，每件要么整件拿要么不拿（像金锭）。
  • 分数背包：可以拿一部分（像金粉）。

分数背包可以贪心：按单位重量价值 \(v_i/w_i\) 从高到低装，装满为止，\(O(n\lg n)\)（习题 16.2-6 用线性时间选择可做到 \(O(n)\)）。

0-1 背包不能贪心（原书图 16.2）：容量 50；商品 1 重 10、值 60（6/磅），商品 2 重 20、值 100（5/磅），商品 3 重 30、值 120（4/磅）。贪心先拿商品 1，但最优解是商品 2 和 3，值 220；含商品 1 的方案最多 180。分数背包下贪心依次拿商品 1、2 和 20 磅商品 3，值 240，正是最优。

0-1 问题中贪心失败的原因是：拿了商品 1 后背包装不满，空出来的容量拉低了整体的单位价值。要决定是否装某件商品，必须比较"装它的子问题"和"不装它的子问题"——这产生大量重叠子问题，正是动态规划的标志。0-1 背包的 DP 是 \(O(nW)\)（习题 16.2-2），注意这是伪多项式时间：\(W\) 是数值而非输入长度。

白话解释：分数背包能贪心、0-1 背包不能，差别只在"能不能切"。能切时，背包永远可以被单位价值最高的东西填满，不存在"剩下一块空间浪费掉"的问题；不能切时，先拿单位价值最高的东西可能留下一块尴尬的空位，其他东西都塞不进去，整体单位价值被拉低。 金融直觉：大资金按权重配置时，股票几乎可以任意切分，近似分数背包，按 alpha/风险排序就够了；小资金买高价股时，一手就是十几万元，这就是 0-1 背包——你买了一手贵州茅台级别的股票，剩下的预算可能什么都配不齐。 "伪多项式"的意思：\(O(nW)\) 看起来是多项式，但 \(W\) 是一个数值。预算从 20 万元变成 2000 万元，输入只多了两位数字，计算量却放大 100 倍。所以代码里把预算按 100 元一档离散化，就是在控制 \(W\) 的大小。

16.2.4 几道贪心习题

  • 补水站问题（习题 16.2-4）：带的水只够滑 \(m\) 英里，在水用完前尽量走到最远的补水点，最少补水次数，\(O(n)\)。
  • 单位区间覆盖（习题 16.2-5）：排序后从最左未覆盖点放区间。
  • 排序不等式（习题 16.2-7）：两组正数任意配对，最大化 \(\prod a_i^{b_i}\)——把两组都按同一顺序排序配对。它的量化版本是：把更大的权重分配给更强的信号，能最大化加权和。

16.3 Huffman 编码

16.3.1 前缀码与码树

一个 100,000 字符的文件只含 a–f 六个字符，频率（千次）如下：

字符 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,000 位；变长码需要 \((45\cdot1+13\cdot3+12\cdot3+16\cdot3+9\cdot4+5\cdot4)\times1000=224{,}000\) 位，节省约 25%，而且这是该文件的最优字符编码。

前缀码（prefix code）：任何码字都不是另一个码字的前缀。前缀码总能达到字符编码中的最优压缩，所以只研究前缀码不失一般性。编码时直接拼接码字；解码时开头的码字是唯一确定的，例如 001011101 唯一地分解为 0·0·101·1101，解码为 aabe。

前缀码可以用一棵二叉树表示：叶子是字符，从根到叶的路径就是码字（左 0 右 1）。最优编码总对应一棵满二叉树（每个内部结点恰有两个孩子；定长码的树不满，因为没有以 11 开头的码字，所以不是最优）。设字符 \(c\) 的频率为 \(c.freq\)、在树 \(T\) 中的深度为 \(d_T(c)\)，编码文件的总位数（树的代价）是

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

白话解释：先说清"树"在这里是什么。从一个起点（根）出发，每次往左走记一个 0、往右走记一个 1，走到尽头（叶子）就是一个字符。走了几步，码字就有几位，这个步数叫"深度" \(d_T(c)\)。\(B(T)\) 就是"每个字符出现的次数 × 它的码字长度"再加总，也就是整个文件编码后的总位数。用上表变长码检验：\(45\times1+13\times3+12\times3+16\times3+9\times4+5\times4=224\)（千位）。 目标因此很直观：出现越多的字符，应该放得越浅（码越短）。这与"高频交易品种的数据要放在最快的存储里"是同一种权衡。

16.3.2 算法

Huffman 算法自底向上构造码树：用以频率为键的最小优先队列，反复取出频率最低的两个结点合并，新结点频率为两者之和，共 \(|C|-1\) 次合并。

def HUFFMAN(C):
    n = len(C)
    Q = MinPriorityQueue(C)          # BUILD-MIN-HEAP，O(n)
    for i in range(1, n):            # n-1 次合并
        z = Node()
        z.left  = x = Q.extract_min()
        z.right = y = Q.extract_min()
        z.freq  = x.freq + y.freq
        Q.insert(z)
    return Q.extract_min()

原书图 16.5：依次合并 f+e=14；c+b=25；14+d=30；25+30=55；a+55=100，得到 a=0、c=100、b=101、f=1100、e=1101、d=111。用二叉堆实现时间 \(O(n\lg n)\)（堆的实现见本册第 06 章）。

16.3.3 正确性

引理 16.2（贪心选择性质）：设 \(x,y\) 是频率最低的两个字符，则存在一个最优前缀码，其中 \(x,y\) 的码字等长且只在最后一位不同。

证明（交换论证）. 取任一最优树 \(T\)，设 \(a,b\) 是最大深度的一对兄弟叶。不妨设 \(a.freq\le b.freq\)、\(x.freq\le y.freq\)，于是 \(x.freq\le a.freq\)、\(y.freq\le b.freq\)。交换 \(a\) 与 \(x\) 得 \(T'\)：

\[B(T)-B(T')=(a.freq-x.freq)\big(d_T(a)-d_T(x)\big)\ge0,\]
因为 \(x\) 频率最小、\(a\) 深度最大。同理交换 \(b\) 与 \(y\) 得 \(T''\)，\(B(T')-B(T'')\ge0\)。所以 \(B(T'')\le B(T)\)，又 \(T\) 最优，\(T''\) 也最优，且 \(x,y\) 是其中最大深度的兄弟。\(\square\)

推导拆解：\(B(T)-B(T')\) 这个式子是怎么来的？交换 \(a\) 与 \(x\) 只改变这两个字符的深度，其他字符的项在相减时全部抵消，只剩 \(B(T)-B(T')=\big[x.freq\cdot d_T(x)+a.freq\cdot d_T(a)\big]-\big[x.freq\cdot d_T(a)+a.freq\cdot d_T(x)\big]\)。 把含 \(a.freq\) 的项、含 \(x.freq\) 的项各自合并，就得到 \((a.freq-x.freq)\big(d_T(a)-d_T(x)\big)\)。两个括号都 \(\ge0\)（\(x\) 最不常用、\(a\) 最深），所以乘积 \(\ge0\)，即交换后总位数不增加。 直观含义就是排序不等式：把"更常用"配给"更浅"，总代价一定不会更差。

为什么叫"贪心"：把一次合并的代价看作两个被合并项的频率之和，树的总代价恰好等于所有合并代价之和（习题 16.3-4），而 Huffman 每一步都选代价最小的合并。

引理 16.3（最优子结构）：把 \(x,y\) 换成一个频率为 \(x.freq+y.freq\) 的新字符 \(z\)，得到字母表 \(C'\)。若 \(T'\) 是 \(C'\) 的最优树，则把 \(T'\) 中的叶 \(z\) 替换为以 \(x,y\) 为孩子的内部结点所得的 \(T\) 是 \(C\) 的最优树。

证明要点. \(B(T)=B(T')+x.freq+y.freq\)。若有更好的 \(T''\)，由引理 16.2 可设 \(x,y\) 在其中是兄弟，把它们合并回 \(z\) 就得到比 \(T'\) 更好的 \(C'\) 的树，矛盾。\(\square\)

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

常见误区：码树不是二叉搜索树；Huffman 只在"逐字符编码"这一类方法中最优（与上下文相关的编码可以更好）；频率相同时平局可任意打破，码字不同但代价相同。习题 16.3-8 指出：若 256 个字符的频率都很接近（最大频率不到最小频率的 2 倍），Huffman 不比 8 位定长码好；习题 16.3-9 用计数论证说明随机文件不可能被压缩。

16.4 拟阵与贪心方法（选读）

本节给出一个刻画"何时贪心必定最优"的理论。它不能覆盖所有贪心问题（活动选择和 Huffman 不在其内），但覆盖了很多实际情形，而且在组合选股中非常好用。

16.4.1 定义

**拟阵（matroid）**是有序对 \(M=(S,\mathcal I)\)，满足：

  1. \(S\) 是有限集；
  2. \(\mathcal I\) 是 \(S\) 的一族非空子集，称为独立子集，并满足遗传性：若 \(B\in\mathcal I\) 且 \(A\subseteq B\)，则 \(A\in\mathcal I\)（于是 \(\emptyset\in\mathcal I\)）；
  3. 交换性质：若 \(A,B\in\mathcal I\) 且 \(|A|<|B|\)，则存在 \(x\in B-A\) 使 \(A\cup\{x\}\in\mathcal I\)。

白话解释：把 \(S\) 想成股票池，\(\mathcal I\)（花体 I，取自 independent）是"所有满足约束的持仓组合"构成的清单，清单里的每个组合叫"独立集"。三条要求翻译过来： (1) 股票池有限。 (2) 遗传性：一个合规组合删掉几只股票后仍然合规。"每个行业至多 1 只"满足这一点；"必须恰好持有 10 只"就不满足。 (3) 交换性：如果组合 \(B\) 比组合 \(A\) 大，那么总能从 \(B\) 里找一只 \(A\) 没有的股票加进 \(A\)，且加完仍然合规。以"每个行业至多 1 只"为例：\(A\) 覆盖 2 个行业，\(B\) 覆盖 3 个行业，\(B\) 中必有一只股票属于 \(A\) 没碰过的行业，把它加进 \(A\) 不违规。 交换性就是保证"贪心不会把自己堵死"的那条性质：只要还有更大的合规组合存在，当前组合就一定还能再扩。资金约束为什么破坏它？\(A\) 是一只 15 万元的股票，\(B\) 是两只各 9 万元的股票，预算 20 万元：\(|A|<|B|\)，但 \(B\) 中任何一只加进 \(A\) 都超预算。

例子：

  • 矩阵拟阵：\(S\) 为矩阵的列，线性无关的列集为独立集（习题 16.4-2）。"拟阵"一词由此而来。
  • 图拟阵：\(S\) 为无向图的边，无环边集（森林）为独立集。定理 16.5 证明它是拟阵，交换性的关键是：森林恰含 \(|V|-|A|\) 棵树，边更多的森林树更少，必有一条边连接 \(A\) 的两棵不同的树。
  • 均匀拟阵：大小不超过 \(k\) 的子集为独立集（习题 16.4-1）。
  • 划分拟阵：\(S\) 被划分为若干块，每块至多取一个（或至多 \(c_j\) 个）的子集为独立集（习题 16.4-4）。

若 \(A\cup\{x\}\) 独立（\(x\notin A\)），称 \(x\) 是 \(A\) 的扩张；没有扩张的独立集称为极大的。定理 16.6：拟阵中所有极大独立子集大小相同（否则交换性会给小的那个找到扩张）。连通图的极大独立集就是生成树。

16.4.2 加权拟阵上的贪心

给每个元素一个严格正的权重 \(w(x)\)，\(w(A)=\sum_{x\in A}w(x)\)。要找权重最大的独立集（最优子集）。权重为正，所以最优子集必是极大独立集。

def GREEDY(M, w):
    A = set()
    for x in sorted(M.S, key=w, reverse=True):   # 按权重递减
        if is_independent(A | {x}):              # 独立性检查，设耗时 f(n)
            A.add(x)
    return A

时间 \(O(n\lg n+nf(n))\)。

定理 16.11：GREEDY 在加权拟阵上返回最优子集。证明由三步组成：

  • 引理 16.7（贪心选择性质）：设 \(x\) 是按权递减顺序第一个使 \(\{x\}\) 独立的元素，则存在包含 \(x\) 的最优子集。取任一最优子集 \(B\)，若 \(x\notin B\)，从 \(\{x\}\) 出发用交换性不断从 \(B\) 中加元素直到与 \(B\) 等大，得到 \(A=B-\{y\}\cup\{x\}\)，\(w(A)\ge w(B)\)。
  • 推论 16.9：一开始就不能单独构成独立集的元素，以后也永远加不进去——跳过它们不会出错（遗传性）。
  • 引理 16.10（最优子结构）：选了 \(x\) 之后，剩下的问题是在收缩拟阵 \(M'\) 上求最优子集，\(M'\) 仍是拟阵。

推导拆解：引理 16.7 的证明为什么得到 \(w(A)\ge w(B)\)？从 \(\{x\}\) 出发，每次用交换性从 \(B\) 里挑一个元素加进来，直到和 \(B\) 一样大。这样得到的 \(A\) 与 \(B\) 只差一个元素：\(A\) 有 \(x\)，\(B\) 有某个 \(y\)。而 \(x\) 是"按权重从大到小第一个能单独成立的元素"，\(y\) 单独也能成立（遗传性：\(B\) 合规，\(\{y\}\) 也合规），所以 \(w(x)\ge w(y)\)，于是 \(w(A)=w(B)-w(y)+w(x)\ge w(B)\)。 "收缩"可以理解为：把 \(x\) 永久放进组合，剩下的问题是"在已经持有 \(x\) 的前提下，继续往里加什么"。这个剩余问题仍满足三条性质，于是可以对它再贪心一次，一路归纳下去。

最小生成树可以化归为这个框架：取 \(w'(e)=w_0-w(e)\)（\(w_0\) 大于所有边权），最大化 \(w'\) 等价于最小化 \(w\)，GREEDY 就是 Kruskal 算法（本册图算法相关章节）。习题 16.4-5 说明了"最小权极大独立集"问题的一般转化方法。

16.5 用拟阵解任务调度问题（选读）

单处理器上调度 \(n\) 个单位时间任务，任务 \(a_i\) 有整数截止时间 \(d_i\) 和非负罚款 \(w_i\)，未在截止时间前完成就罚 \(w_i\)。目标是最小化总罚款。

规范化：可以把"早"任务（按时完成的）排在"迟"任务前面，并把早任务按截止时间递增排列，都不改变罚款。所以问题等价于选一个早任务集合 \(A\)。若存在使 \(A\) 中无任务迟到的调度，称 \(A\) 独立。

引理 16.12：设 \(N_t(A)\) 为 \(A\) 中截止时间 \(\le t\) 的任务数。以下等价：(1) \(A\) 独立；(2) 对所有 \(t\)，\(N_t(A)\le t\)；(3) 把 \(A\) 按截止时间递增调度，没有任务迟到。用 (2) 可在 \(O(|A|)\) 时间判断独立性（计数后求前缀和）。

白话解释：\(N_t(A)\le t\) 的意思是"截止时间在第 \(t\) 天及以前的任务，不能超过 \(t\) 个"，因为前 \(t\) 天最多只做得完 \(t\) 个单位任务。以原书例检验：若 \(A=\{a_1,a_2,a_3,a_4,a_6\}\)，它们的截止时间是 4、2、4、3、4，\(N_4(A)=5>4\)，必有一个迟到，所以不独立。这就像"在某个日期前到期的债务总额不能超过该日期前可用的现金"：逐个日期检查累计需求是否超过累计供给。

定理 16.13：\((S,\mathcal I)\) 是拟阵。于是"最小化迟任务罚款"="最大化早任务罚款"，按罚款递减贪心即可，\(O(n^2)\)（思考题 16-4 用不相交集合森林可做到近线性）。

原书例（图 16.7）：

\(a_i\) 1 2 3 4 5 6 7
\(d_i\) 4 2 4 3 1 4 6
\(w_i\) 70 60 50 40 30 20 10

贪心接受 \(a_1,a_2,a_3,a_4\)，拒绝 \(a_5\) 和 \(a_6\)（加入后 \(N_4=5>4\)），接受 \(a_7\)。最优调度 \(\langle a_2,a_4,a_1,a_3,a_7,a_5,a_6\rangle\)，总罚款 \(w_5+w_6=50\)。

16.6 原书思考题速览

  • 16-1 找零：美国硬币（25、10、5、1 美分）贪心最优；面额为 \(c^0,\dots,c^k\) 时贪心最优；但面额 \(\{1,3,4\}\) 找 6 时贪心给出 \(4+1+1\)，最优是 \(3+3\)；一般面额要用 \(O(nk)\) 的 DP。
  • 16-2 最小化平均完成时间：非抢占时按处理时间最短优先（SPT）；有释放时间且允许抢占时按剩余处理时间最短优先（SRPT）。原书例：\(p_1=3,p_2=5\)，先 \(a_1\) 平均完成时间 5.5，先 \(a_2\) 为 6.5。
  • 16-3 无环子图：有向图中"不含有向环的边集"一般不构成拟阵。
  • 16-4 调度变体：按罚款递减，把每个任务放进截止时间之前最晚的空槽。
  • 16-5 离线缓存：已知全部请求序列时，缓存未命中时驱逐"下次访问最远"的元素（furthest-in-future），未命中次数最少。

16.7 量化实战

16.7.1 验证原书三个例子

import heapq, itertools, numpy as np

# ---------- 活动选择：原书 16.1 的 11 个活动 ----------
s = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]; f = [4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
def greedy_activity_selector(s, f):           # 已按结束时间排序
    A, k = [1], 0
    for m in range(1, len(s)):
        if s[m] >= f[k]: A.append(m + 1); k = m
    return A
print("活动选择:", [f"a{i}" for i in greedy_activity_selector(s, f)])

# ---------- Huffman 编码：原书图 16.3/16.5 ----------
def huffman(freq):
    cnt = itertools.count()                    # 频率相同时用计数器打破平局
    Q = [(w, next(cnt), c) for c, w in freq.items()]; heapq.heapify(Q)
    for _ in range(len(freq) - 1):             # n-1 次合并
        w1, _, x = heapq.heappop(Q); w2, _, y = heapq.heappop(Q)
        heapq.heappush(Q, (w1 + w2, next(cnt), (x, y)))
    code = {}
    def walk(t, pre):
        if isinstance(t, tuple): walk(t[0], pre + "0"); walk(t[1], pre + "1")
        else: code[t] = pre or "0"
    walk(Q[0][2], ""); return code
freq = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
code = huffman(freq)
print("Huffman 码:", dict(sorted(code.items())),
      " 总位数(千):", sum(freq[c] * len(code[c]) for c in freq), " 定长码:", 3 * sum(freq.values()))

# ---------- 带截止时间与罚款的单位任务调度：原书图 16.7 ----------
d = [4, 2, 4, 3, 1, 4, 6]; w = [70, 60, 50, 40, 30, 20, 10]
def independent(A):                            # 引理 16.12：对所有 t，N_t(A) <= t
    cnt = np.bincount([d[i] for i in A], minlength=len(d) + 1)
    return np.all(np.cumsum(cnt) <= np.arange(len(d) + 1))
A = []
for i in sorted(range(len(d)), key=lambda i: -w[i]):   # 按罚款递减，能保持独立就加入
    if independent(A + [i]): A.append(i)
early = sorted(A, key=lambda i: d[i]); late = [i for i in range(len(d)) if i not in A]
print("最优调度:", [f"a{i+1}" for i in early + late], " 总罚款:", sum(w[i] for i in late))

运行输出：

活动选择: ['a1', 'a4', 'a8', 'a11']
Huffman 码: {'a': '0', 'b': '101', 'c': '100', 'd': '111', 'e': '1101', 'f': '1100'}  总位数(千): 224  定长码: 300
最优调度: ['a2', 'a4', 'a1', 'a3', 'a7', 'a5', 'a6']  总罚款: 50

三个结果都与原书一致（Huffman 码字也与图 16.5 完全相同）。

16.7.2 行情压缩、拟阵选股与贪心的边界

下面的代码做三件事。

(1) 逐笔价格变动的 Huffman 压缩。 以最小变动价位计，逐笔成交价的变动绝大多数是 0 或 ±1 个 tick，分布高度集中——正是变长码的用武之地。代码比较定长码、Huffman 码与信息熵（任何逐符号编码平均码长的下界）。

白话解释：信息熵 \(H=-\sum_i p_i\log_2p_i\) 衡量"一个符号平均带来多少位的意外"。概率为 \(p\) 的符号理想码长是 \(-\log_2p\) 位：概率 \(1/2\) 的用 1 位，概率 \(1/8\) 的用 3 位；按概率加权平均就是 \(H\)。例：只有两种变动 0 和 1，各占一半，\(H=1\) 位；若 0 占 90%、1 占 10%，\(H=-(0.9\log_20.9+0.1\log_20.1)\approx0.47\) 位，分布越集中，可压缩空间越大。Huffman 的码长必须是整数，所以只能接近 \(H\)，不能低于它。

(2) 拟阵约束下贪心选股最优；背包约束下贪心失效。 "每个行业至多 1 只、总数至多 \(K\) 只"是一个截断的划分拟阵（拟阵截断后仍是拟阵），所以按信号强度从高到低、能选就选，一定得到信号总和最大的组合——用暴力枚举验证。但 A 股按手（100 股）交易，高价股一手可能要十几万元。小资金账户在"每只至多一手、总资金不超过预算"约束下最大化预期超额收益，就是 0-1 背包：按收益率或收益额贪心都不保证最优，需要 DP。

(3) 区间调度：数量最多 vs 价值最大。 把一系列事件驱动的交易机会看作时间区间（同一时间只能占用一个交易通道或一份风险预算），"最早结束优先"能做最多笔，但若各机会预期收益不同，要用加权区间调度 DP。

import heapq, itertools, bisect, numpy as np
from itertools import combinations
rng = np.random.default_rng(16)

# ---------- 1. Huffman 压缩逐笔价格变动（以最小变动价位计） ----------
def huffman_lengths(freq):
    cnt = itertools.count()
    Q = [(w, next(cnt), [c]) for c, w in freq.items()]; heapq.heapify(Q)
    depth = {c: 0 for c in freq}
    while len(Q) > 1:
        w1, _, s1 = heapq.heappop(Q); w2, _, s2 = heapq.heappop(Q)
        for c in s1 + s2: depth[c] += 1        # 每合并一次，子树内所有叶深度 +1
        heapq.heappush(Q, (w1 + w2, next(cnt), s1 + s2))
    return depth
ticks = np.clip(np.round(rng.laplace(0, 0.8, 1_000_000)), -15, 15).astype(int)   # 逐笔变动：多为 0、±1
vals, cnts = np.unique(ticks, return_counts=True)
L = huffman_lengths(dict(zip(vals.tolist(), cnts.tolist())))
pr = cnts / cnts.sum()
avg = sum(pr[i] * L[v] for i, v in enumerate(vals.tolist()))
H = -(pr * np.log2(pr)).sum()
print(f"变动取值 {len(vals)} 种: 定长码 {int(np.ceil(np.log2(len(vals))))} 位/笔, Huffman {avg:.3f} 位/笔, 熵 {H:.3f} 位/笔")
print("码长:", {v: L[v] for v in [-2, -1, 0, 1, 2, int(vals.max())]})

# ---------- 2. 拟阵约束下的贪心选股 vs 背包约束下贪心失效 ----------
n, K = 12, 4
score = np.round(rng.normal(0, 1, n), 2)                    # 信号强度（可看作预期超额收益排名分）
industry = rng.integers(0, 5, n)                             # 5 个行业
def greedy_partition(score, industry, K):                    # 每行业至多 1 只、总数至多 K：截断划分拟阵
    A, used = [], set()
    for i in np.argsort(-score):
        if score[i] <= 0: break                              # 权重须为正（拟阵贪心的前提）
        if industry[i] not in used and len(A) < K: A.append(i); used.add(industry[i])
    return A
A = greedy_partition(score, industry, K)
best = max((sum(score[list(c)]) for r in range(K + 1) for c in combinations(range(n), r)
            if len(set(industry[list(c)])) == len(c)), default=0)
print(f"\n拟阵贪心: 选 {sorted(int(i) for i in A)}（行业 {[int(industry[i]) for i in sorted(A)]}），得分 {score[A].sum():.2f}；暴力最优 {best:.2f}")

price = np.array([1650.0, 38.2, 12.5, 210.0, 75.0, 9.8, 560.0, 18.0, 46.0, 130.0, 25.0, 88.0])
cost = price * 100                                           # A 股一手 100 股，每只至多买 1 手
alpha = np.abs(score) * 0.01 + 0.002                         # 每只股票的预期超额收益率（均为正）
value = alpha * cost                                         # 预期超额收益（元）
budget = 200_000
def greedy_by(key):
    A, left = [], budget
    for i in np.argsort(-key):
        if cost[i] <= left: A.append(i); left -= cost[i]
    return value[A].sum()
def knapsack(cost, value, W, unit=100):                      # 0-1 背包 DP：O(n·W/unit)
    c = (np.ceil(cost / unit)).astype(int); Wd = W // unit
    best = np.zeros(Wd + 1)
    for i in range(len(c)):
        best[c[i]:] = np.maximum(best[c[i]:], best[:Wd + 1 - c[i]] + value[i])   # 右侧先整体求值，等价于逆序更新：每只至多选一次
    return best[Wd]
print(f"资金 {budget:,} 元、整手约束：按收益率贪心 {greedy_by(alpha):,.0f} 元 | 按收益额贪心 {greedy_by(value):,.0f} 元"
      f" | 背包 DP 最优 {knapsack(cost, value, budget):,.0f} 元")

# ---------- 3. 区间调度：最多个数（贪心） vs 最大总价值（DP + 二分，习题 16.1-5） ----------
m = 300
st = np.sort(rng.uniform(0, 1000, m)); fi = st + rng.exponential(20, m)
val = rng.lognormal(0, 1, m)                                  # 每个事件交易机会的预期收益
order = np.argsort(fi); st, fi, val = st[order], fi[order], val[order]
cnt_sel, last = [], -np.inf
for i in range(m):                                            # 最早结束优先
    if st[i] >= last: cnt_sel.append(i); last = fi[i]
dp = np.zeros(m + 1)                                          # dp[j]：前 j 个区间的最大总价值
for j in range(1, m + 1):
    pj = bisect.bisect_right(fi, st[j - 1], 0, j - 1)         # 结束时间 <= s_j 的区间个数
    dp[j] = max(dp[j - 1], dp[pj] + val[j - 1])
print(f"\n{m} 个事件窗口：贪心选 {len(cnt_sel)} 个，总价值 {val[cnt_sel].sum():.1f}；加权 DP 最优总价值 {dp[m]:.1f}")

运行输出：

变动取值 21 种: 定长码 5 位/笔, Huffman 2.233 位/笔, 熵 2.180 位/笔
码长: {-2: 5, -1: 3, 0: 1, 1: 2, 2: 4, 11: 20}

拟阵贪心: 选 [0, 3, 7, 8]（行业 [1, 3, 4, 0]），得分 5.07；暴力最优 5.07
资金 200,000 元、整手约束：按收益率贪心 1,400 元 | 按收益额贪心 2,170 元 | 背包 DP 最优 2,201 元

300 个事件窗口：贪心选 91 个，总价值 151.4；加权 DP 最优总价值 196.3

读结果。

  • 压缩：Huffman 码平均 2.233 位/笔，离熵下界 2.180 只差 2.4%，比 5 位定长码省一半以上。最常见的"0 变动"只用 1 位，极少出现的大跳动用到 20 位——但它们几乎不出现，对平均码长没有影响。实际的行情存储系统多用通用压缩库（如 zstd、LZ4）配合差分编码，它们内部同样使用熵编码；理解 Huffman 能帮你判断"先做差分再压缩"为什么有效：差分把数据变成高度集中的分布。
  • 拟阵选股：贪心结果与暴力枚举一致。只要约束是"每组至多若干只""总数至多若干只"这类拟阵约束，且目标是信号的加权和，按信号从强到弱选就是最优，不需要整数规划。
  • 背包选股：加上资金和整手约束后，按收益率贪心只得到最优值的 64%（它先选了收益率最高、但价格较低的股票，最后剩下的钱不够买别的）；按收益额贪心接近但仍不是最优。整手约束对小资金账户和高价股影响很大，这时需要 DP 或整数规划（第 04 册）。
  • 区间调度：最早结束优先选出了最多的 91 个机会，但总价值只有 151.4；加权 DP 选出的组合总价值 196.3，高约 30%。目标是"做最多笔"还是"赚最多钱"，决定了能不能用贪心。

16.7.3 回测数据缓存：LRU 与离线最优

思考题 16-5 证明了"驱逐下次访问最远的元素"在离线情形下最优。它在实际中无法直接使用（不知道未来请求），却是评估在线策略的基准。回测框架按需加载"因子 × 月份"之类的数据块时，可以拿它衡量 LRU 离理论最优还有多远：

import numpy as np
from collections import OrderedDict
rng = np.random.default_rng(165)

# 回测中按需加载的数据块（如 某因子×某月 的面板），访问呈"热点 + 顺序扫描"混合
hot = rng.zipf(1.3, 20000) % 200                       # 热点块：少数块被反复访问
scan = np.arange(20000) % 500 + 200                    # 顺序扫描：逐月遍历历史数据
req = np.where(rng.random(20000) < 0.6, hot, scan)

def lru_misses(req, k):
    cache, miss = OrderedDict(), 0
    for r in req:
        if r in cache: cache.move_to_end(r)
        else:
            miss += 1
            if len(cache) >= k: cache.popitem(last=False)   # 驱逐最久未用的
            cache[r] = True
    return miss

def furthest_in_future_misses(req, k):                  # 思考题 16-5：驱逐下次访问最远的块（离线最优）
    n = len(req); nxt = np.empty(n, dtype=np.int64); last = {}
    for i in range(n - 1, -1, -1):                      # 预处理每个位置的"下次访问时刻"
        nxt[i] = last.get(req[i], n + i); last[req[i]] = i
    cache, miss = {}, 0                                 # 块 → 下次访问时刻
    for i, r in enumerate(req):
        if r not in cache:
            miss += 1
            if len(cache) >= k:
                victim = max(cache, key=cache.get)      # O(k) 找最远者；可用堆优化到 O(lg k)
                del cache[victim]
        cache[r] = nxt[i]
    return miss

for k in [20, 50, 100]:
    print(f"缓存 {k:3d} 块: LRU 未命中 {lru_misses(req, k):5d} | 最远将来(离线最优) {furthest_in_future_misses(req, k):5d}")

运行输出：

缓存  20 块: LRU 未命中 14689 | 最远将来(离线最优) 11266
缓存  50 块: LRU 未命中 12980 | 最远将来(离线最优)  9735
缓存 100 块: LRU 未命中 11827 | 最远将来(离线最优)  7810

在"热点 + 顺序扫描"混合的访问模式下，LRU 的未命中比离线最优多 30%–50%，缓存越大差距越明显：顺序扫描会把热点块挤出 LRU 缓存，而离线最优知道扫描到的块短期内不会再被访问。这提示两个实用改进：把顺序扫描与随机访问分开缓存；或者在回测这种请求序列事先可知的场景（回测要读哪些数据通常在开始前就能确定），直接用"最远将来"策略预取和驱逐。

本章小结

贪心算法每步做局部最优选择，正确性依赖贪心选择性质（通常用交换论证证明存在包含贪心选择的最优解）和最优子结构。活动选择按最早结束优先 \(\Theta(n)\)（排序 \(O(n\lg n)\)）；分数背包按单位价值贪心，而 0-1 背包必须用 \(O(nW)\) 的 DP；Huffman 编码反复合并频率最低的两棵树，\(O(n\lg n)\)，在逐字符编码中最优。拟阵理论给出一个充分条件：在加权拟阵上，"按权递减、能加就加"必定得到最优子集；均匀拟阵、划分拟阵、图拟阵、单位任务调度都是拟阵。量化中，"每组至多若干只"的选股约束是拟阵，贪心最优；资金与整手约束是背包，加权的事件调度是带权区间问题，贪心失效，需要 DP。

问题 方法 复杂度 关键性质
活动选择（最多个数） 最早结束优先 \(\Theta(n)\)（已排序） 定理 16.1，交换论证
加权区间调度 DP + 二分 \(O(n\lg n)\) 贪心失效
分数背包 按 \(v_i/w_i\) 贪心 \(O(n\lg n)\) 贪心选择性质
0-1 背包 DP \(O(nW)\)（伪多项式） 重叠子问题
Huffman 编码 最小堆反复合并 \(O(n\lg n)\) 引理 16.2、16.3；\(B(T)=\sum c.freq\cdot d_T(c)\)
加权拟阵最优子集 GREEDY \(O(n\lg n+nf(n))\) 遗传性 + 交换性（定理 16.11）
单位任务调度 按罚款递减贪心 \(O(n^2)\) \(N_t(A)\le t\)（引理 16.12）
离线缓存 最远将来 — 思考题 16-5

练习

基础

  1. 举反例说明以下贪心策略对活动选择问题不正确：选持续时间最短的；选与其他活动重叠最少的；选最早开始的。（原书 16.1-3。）
  2. 改为"每次选与已选活动兼容、开始最晚的活动"，证明它也是最优的。（原书 16.1-2。）
  3. 写出 0-1 背包的 \(O(nW)\) 动态规划，并在原书图 16.2 的数据上验证最优值 220。（原书 16.2-2。）
  4. 以前 8 个 Fibonacci 数 1, 1, 2, 3, 5, 8, 13, 21 为频率求 Huffman 码，并推广到前 \(n\) 个 Fibonacci 数。（原书 16.3-3。提示：树是一条"链"。）
  5. 证明 Huffman 树的代价等于所有内部结点（即所有合并）的频率之和。（原书 16.3-4。）

进阶

  1. 证明分数背包具有贪心选择性质。（原书 16.2-1。）
  2. 设计用最少教室安排所有活动的贪心算法，并说明所需教室数等于最大重叠数。量化中它能回答什么问题？（原书 16.1-4。提示：同时运行的事件策略最少需要多少份独立的风险预算或交易通道。）
  3. 证明"每个行业至多 \(c_j\) 只、总数至多 \(K\) 只"的选择约束构成拟阵。若再加上"总资金不超过预算"，为什么不再是拟阵？构造一个违反交换性质的例子。
  4. 用面额 \(\{1,3,4\}\) 说明找零贪心不最优，并写出 \(O(nk)\) 的 DP。（原书思考题 16-1。）
  5. 证明思考题 16-5：离线缓存中"最远将来"策略的未命中次数最少。
  6. 思考题 16-2：说明为什么按处理时间最短优先（SPT）能最小化平均完成时间。若一批回测任务要在单机上串行运行，研究员希望平均等待时间最短，应如何排序？

原书推荐习题：16.1-3、16.1-4、16.1-5、16.2-2、16.2-4、16.2-7、16.3-3、16.3-4、16.3-8、16.3-9、16.4-2、16.4-4、16.4-5、16.5-2，思考题 16-1、16-2、16-5。

原书对照

本章小节 原书章节 PDF 页码
16.1 活动选择问题 16.1 An activity-selection problem p.436–443
16.2 贪心策略的要素 16.2 Elements of the greedy strategy p.444–449
16.3 Huffman 编码 16.3 Huffman codes p.449–458
16.4 拟阵与贪心方法 16.4 Matroids and greedy methods p.458–464
16.5 任务调度 16.5 A task-scheduling problem as a matroid p.464–467
16.6 思考题速览 Problems 16-1～16-5、章末注记 p.467–471