第 35 章近似算法

本章对应原书第 35 章。上一章说明，许多重要的组合优化问题是 NP 难的，几乎不可能有多项式时间的精确算法。但"NP 难"不等于"没办法"：很多问题存在多项式时间算法，能保证解不会比最优差太多。本章讲近似比的定义、证明近似比的通用套路（找最优值的下界），以及五类经典结果：顶点覆盖、旅行商、集合覆盖、随机化与线性规划舍入、子集和的完全多项式时间近似方案。量化实战把它们落到对冲工具选择、按整手凑目标金额、资金约束下选择交易机会、回测任务调度等具体问题上。

学习目标

读完本章，你应当能够：

写出近似比 $\rho(n)$ 的定义，区分 PTAS 与 FPTAS，并说明近似比是最坏情况保证。
掌握证明近似比的套路：先找一个可计算的最优值界（极大匹配、最小生成树、LP 松弛、全部子句数），再把算法解与这个界联系起来。
复述顶点覆盖的 2-近似、三角不等式 TSP 的 2-近似、一般 TSP 不可常数近似的间隙归约、集合覆盖贪心的 $H(\max|S|)$ 近似、MAX-3-CNF 的随机 8/7-近似、加权顶点覆盖的 LP 舍入 2-近似。
理解子集和 FPTAS 的"修剪"思想，并能用它在资金凑整、订单拆分中控制动态规划的状态数。
在量化场景中使用贪心集合覆盖、背包 2-近似、并行机调度贪心，并能用 LP 下界或简单下界评估启发式解离最优还有多远。

读前导读

这一章在解决什么问题

上一章的结论是：带离散决策的组合问题（选哪几只股票、买几手、选哪些交易机会）多半是 NP 难的，求精确最优解可能要花指数时间。这一章回答接下来的问题：既然求不到精确最优，能不能快速求一个"保证不会差太多"的解？

关键词是"保证"。量化实务里到处是启发式：按收益率从高到低装资金、先选覆盖面最广的对冲工具、把任务依次分给空闲的机器。它们通常表现不错，但偶尔会在特定结构上崩溃（35.8.4 节有一个例子：朴素贪心只拿到 2，而最优是 100）。近似算法的价值在于给出最坏情况下的书面保证，例如"无论输入是什么，解的成本不超过最优的 2 倍"。

本章最值得带走的不是某个具体算法，而是证明这类保证的通用套路：我们不知道最优值是多少，但可以算出它的一个下界（或上界），再证明算法的解离这个界不远。 这和风险管理里的思路一致：不知道真实的尾部损失，但可以给它定一个保守的界；也和 MILP 求解器报告的 "MIP gap" 是同一个概念——求解器同时维护"目前找到的最好解"和"最优值不可能好过的界"，两者之差就是还剩多少改进空间。

需要先想起来的数学

1. 期望的线性性。 $E[X+Y]=E[X]+E[Y]$，不论 $X,Y$ 是否独立。35.5.1 节用它算"随机赋值平均能满足多少子句"：每个子句被满足的概率是 $7/8$，$m$ 个子句就期望满足 $7m/8$ 个，无需考虑子句之间的相关性。这和组合期望收益等于各资产期望收益的加权和是同一条性质。见第 00 册第 07 章概率中的分析工具。

2. 调和级数与对数。 $H(d)=1+\frac12+\frac13+\cdots+\frac1d$ 增长得很慢，大约是 $\ln d$：$H(3)=\frac{11}{6}\approx1.83$，$H(10)\approx2.93$，$H(1000)\approx7.49$。见第 00 册第 04 章级数与收敛。

3. $(1+x/n)^n$ 与 $e^x$。 $(1+x/n)^n$ 随 $n$ 增大而增大，极限是 $e^x$。你在连续复利里见过它：年利率 $x$ 按 $n$ 次复利，一年后本息是 $(1+x/n)^n$，$n\to\infty$ 时趋于 $e^x$。35.6.3 节用这个事实控制"每轮丢一点精度，$n$ 轮后总共丢多少"。见第 00 册第 04 章。

4. 线性规划松弛。 把"$x$ 只能取 0 或 1"放宽为"$0\le x\le1$"，就得到一个线性规划，可以快速求解。放宽后可选范围更大，所以最小化问题的 LP 最优值不会高于整数最优值，可以作为下界。见本册第 29 章线性规划。

怎么读这一章

核心必读：35.1（近似比的定义）、35.2（顶点覆盖，最短也最能说明"找下界"的套路）、35.5.2（LP 舍入，与第 29 章直接相连）、35.6.2 的修剪思想、35.8 量化实战及其末尾的三条总结。

第一次可以只看结论：35.3.2 的间隙归约（记住"一般 TSP 不存在常数近似"即可）、35.4.3 集合覆盖近似比的证明（记住"贪心的代价不超过最优的 $\ln|X|+1$ 倍"）、35.6.3 FPTAS 证明的计算细节、35.7 思考题选讲（其中背包 2-近似和并行机调度在 35.8.4 有应用，可以到那里再回来看）。

35.1 近似比与近似方案

面对 NP 完全问题，至少有三条出路：输入规模小时，指数时间算法也可以接受；找出有实际意义、可多项式求解的特殊情形；在多项式时间内求近似最优解。返回近似最优解的算法称为近似算法（approximation algorithm）。

近似比（approximation ratio）：若对任意规模为 $n$ 的输入，算法所得解的代价 $C$ 与最优代价 $C^*$ 满足

\max\left(\frac{C}{C^*},\frac{C^*}{C}\right)\le\rho(n),\tag{35.1}

称算法达到近似比 $\rho(n)$，是一个 $\rho(n)$-近似算法。这个定义同时适用于最小化（$C\ge C^*$，看 $C/C^*$）和最大化（$C\le C^*$，看 $C^*/C$）问题。假设所有解代价为正，比值总不小于 1；1-近似就是精确算法。$\rho$ 与 $n$ 无关时直接说"$\rho$-近似"。

白话解释：式 (35.1) 里的 $\max$ 只是为了让最小化、最大化两种问题都用"比值 $\ge1$"来表达。最小化问题（如成本）中，算法的成本 $C$ 不会低于最优 $C^*$，所以看 $C/C^*$：2-近似意味着成本最多是最优的 2 倍。最大化问题（如收益）中，算法的收益不会高于最优，所以看 $C^*/C$：2-近似意味着收益至少是最优的一半。

这个保证对所有输入都成立，包括故意构造的最坏情况，所以它是一份"最坏情况合同"。它不告诉你平均表现如何；35.8 节会看到实际表现通常比保证好得多。

有的问题有小常数近似比（顶点覆盖为 2），有的已知最好的近似比随 $n$ 增长（集合覆盖约 $\ln n$），有的除非 P = NP 否则不存在任何常数近似比（一般 TSP）。

近似方案（approximation scheme）：输入除实例外还有参数 $\epsilon>0$，对任意固定的 $\epsilon$ 都是 $(1+\epsilon)$-近似算法。

PTAS（多项式时间近似方案）：对任意固定 $\epsilon$，运行时间是 $n$ 的多项式，例如 $O(n^{2/\epsilon})$——$\epsilon$ 变小时时间可能暴涨。
FPTAS（完全多项式时间近似方案）：运行时间关于 $n$ 和 $1/\epsilon$ 都是多项式，例如 $O((1/\epsilon)^2n^3)$——$\epsilon$ 缩小常数倍，时间也只增加常数倍。

35.2 顶点覆盖：极大匹配给出下界

最优顶点覆盖是规模最小的顶点覆盖（每条边至少一个端点在其中）。上一章已证它 NP 难。原书的近似算法简单得出奇：

def approx_vertex_cover(edges):
    C = set()
    for u, v in edges:                 # 依次考察每条边
        if u not in C and v not in C:  # 这条边还没被覆盖
            C |= {u, v}                # 把两个端点都加入
    return C

（原书写法是"任取一条剩余的边，加入两个端点，删去所有被覆盖的边"，与上面按顺序扫描等价。）用邻接表实现，时间 $O(V+E)$。原书图 35.1 的例子：7 个顶点的图，依次选中边 $(b,c),(e,f),(d,g)$，得到 6 个顶点 $\{b,c,d,e,f,g\}$，而最优覆盖 $\{b,d,e\}$ 只有 3 个。

定理 35.1 APPROX-VERTEX-COVER 是多项式时间的 2-近似算法。

证明：设 $A$ 是被选中（触发加入两个端点）的那些边。

$A$ 中任两条边没有公共端点（选中一条边后，与它相邻的边都被覆盖了，不会再被选），所以 $A$ 是一个匹配。任何顶点覆盖——包括最优的 $C^*$——都必须含 $A$ 中每条边的至少一个端点，而这些端点互不相同，所以 $|C^*|\ge|A|$。
每次选中的边两个端点都是新的，$|C|=2|A|$。

于是 $|C|=2|A|\le2|C^*|$。$\square$

这个证明展示了本章反复使用的套路：我们不知道最优值是多少，但能找到它的一个下界（这里是极大匹配的大小），再证明算法的解不超过下界的若干倍。

推导拆解：用原书图 35.1 的数字把证明的两步串起来。算法选中了 3 条边 $(b,c),(e,f),(d,g)$，它们两两没有公共端点，这就是匹配 $A$，$|A|=3$。

下界：任何顶点覆盖都必须覆盖这 3 条边，每条边至少要一个端点，而这 3 条边的端点互不相同，一个顶点不可能同时覆盖其中两条，所以任何覆盖至少有 3 个顶点，即 $|C^*|\ge3$。（实际最优恰好是 3。）

上界：算法每选一条边就加入 2 个顶点，共 $|C|=6=2\times3$。

合起来 $|C|=2|A|\le2|C^*|$。证明全程没有求出 $C^*$，只用了"$C^*$ 至少有多大"这一条信息。

习题提醒了两个反直觉的事实：看似更聪明的"每次选度最高的顶点"启发式反而没有近似比 2（习题 35.1-3）；顶点覆盖与团是互补的，但顶点覆盖有 2-近似并不意味着团也有常数近似（习题 35.1-5）——补关系不保持比值。

35.3 旅行商问题

35.3.1 满足三角不等式：最小生成树给出下界

若代价函数满足三角不等式 $c(u,w)\le c(u,v)+c(v,w)$（跳过中间站不会更贵，平面欧氏距离自然满足），TSP 仍是 NP 完全的（习题 35.2-2），但有简单的 2-近似：

任选根 $r$，用 Prim 算法求最小生成树 $T$；
对 $T$ 做前序遍历，按首次访问的顺序排列顶点，回到起点，作为巡回 $H$。

完全图上时间 $\Theta(V^2)$。原书图 35.2：8 个格点，所得巡回代价约 19.074，最优巡回约 14.715。

定理 35.2 APPROX-TSP-TOUR 是满足三角不等式的 TSP 的多项式时间 2-近似算法。

证明：设最优巡回为 $H^*$。

从 $H^*$ 删去任一条边得到一棵生成树，所以 $c(T)\le c(H^*)$——MST 是最优巡回的下界。
绕树一周的"完整遍历" $W$ 恰好经过每条树边两次，$c(W)=2c(T)\le2c(H^*)$。
$W$ 重复访问顶点，不是巡回。由三角不等式，跳过一次重复访问（从 $u$ 直接走到 $w$）不会增加代价；反复跳过只保留首次访问，正好得到前序序列 $H$，故 $c(H)\le c(W)$。

合起来 $c(H)\le2c(H^*)$。$\square$

白话解释：三步各自的直觉如下。

第一步，"最优巡回删掉一条边就是一棵生成树"：巡回是一个圈，剪断一处就变成一条经过所有点的链，链是生成树的一种。而最小生成树是所有生成树里最便宜的，所以它不比这条链贵，更不比完整的巡回贵（代价非负）。

第二步，"绕树一周"：想象沿着树的外沿走一圈，每条树枝去一次、回一次，总路程正好是树的两倍。

第三步，"抄近路"：绕树一周会多次经过同一个点。三角不等式保证"从 $u$ 直接去 $w$"不比"从 $u$ 经 $v$ 再去 $w$"远，所以跳过已访问的点只会缩短路程。

三角不等式在这里不可缺少。没有它，"抄近路"可能更贵，35.3.2 节说明此时根本不存在常数倍的保证。

原书也说明，这个算法理论上漂亮，实践中通常不是最佳选择；Christofides 算法（在 MST 上加最小权完美匹配）达到 3/2-近似，Arora 与 Mitchell 证明欧氏平面 TSP 有 PTAS。

35.3.2 一般 TSP：不存在常数近似

定理 35.3 若 P ≠ NP，则对任意常数 $\rho\ge1$，一般 TSP 不存在多项式时间 $\rho$-近似算法。

证明（间隙归约）：假设有 $\rho$-近似算法 $A$，用它判定 HAM-CYCLE。给定图 $G=(V,E)$，构造完全图：原图的边代价为 1，非边代价为 $\rho|V|+1$。

若 $G$ 有哈密顿回路，最优巡回代价为 $|V|$，$A$ 返回的巡回代价 $\le\rho|V|$；
若没有，任何巡回都至少用一条非边，代价 $\ge(\rho|V|+1)+(|V|-1)>\rho|V|$。

两种情况之间有一道"间隙"，看 $A$ 的输出是否 $\le\rho|V|$ 就能判定 HAM-CYCLE，推出 P = NP。$\square$

这是一种通用技巧：若能把 NP 难问题的"是"实例映射为最小化问题中值 $\le k$ 的实例、"否"实例映射为值 $>\rho k$ 的实例，那么除非 P = NP，该问题不存在 $\rho$-近似。习题 35.2-2 还提醒：给每条边加一个大常数可以让一般 TSP 满足三角不等式、最优巡回不变，但这不与定理 35.3 矛盾——加常数不保持近似比。

35.4 集合覆盖：贪心与调和数

35.4.1 问题

实例 $(X,\mathcal F)$：有限集 $X$ 和它的子集族 $\mathcal F$，且 $\mathcal F$ 中的集合并起来就是 $X$。求最少的集合 $\mathcal C\subseteq\mathcal F$ 覆盖 $X$。它推广了顶点覆盖（每个顶点看作"它所关联的边"构成的集合），所以 NP 难。原书的例子：$X$ 是解决某问题所需的技能，每个人掌握若干技能，求人数最少、覆盖全部技能的委员会。原书图 35.3：12 个点、6 个集合，最优覆盖 $\{S_3,S_4,S_5\}$ 用 3 个集合，贪心用了 4 个。

35.4.2 贪心算法

每一步选覆盖未覆盖元素最多的集合：

def greedy_set_cover(X, F):
    U, C = set(X), []
    while U:
        i = max(range(len(F)), key=lambda i: len(F[i] & U))   # 平局任意
        U -= F[i]; C.append(i)
    return C

简单实现 $O(|X||\mathcal F|\min(|X|,|\mathcal F|))$；按"新覆盖元素数"分桶维护可做到 $O(\sum_{S\in\mathcal F}|S|)$（习题 35.3-3）。

35.4.3 近似比：代价分摊

记第 $d$ 个调和数 $H(d)=\sum_{i=1}^d1/i$（附录 A：$H(d)\le\ln d+1$）。

定理 35.4 GREEDY-SET-COVER 是 $\rho$-近似算法，$\rho=H(\max\{|S|:S\in\mathcal F\})$。

证明（代价分摊法）：贪心每选一个集合 $S_i$ 付代价 1，把这 1 平均分给 $S_i$ 首次覆盖的元素：若元素 $x$ 首次被 $S_i$ 覆盖，令

c_x=\frac1{|S_i-(S_1\cup\cdots\cup S_{i-1})|}.

于是贪心解的大小 $|\mathcal C|=\sum_{x\in X}c_x$。最优覆盖 $\mathcal C^*$ 中每个元素至少出现一次，所以

|\mathcal C|=\sum_xc_x\le\sum_{S\in\mathcal C^*}\sum_{x\in S}c_x.

关键不等式：对任意 $S\in\mathcal F$，

\sum_{x\in S}c_x\le H(|S|).\tag{35.12}

有了它，$|\mathcal C|\le\sum_{S\in\mathcal C^*}H(|S|)\le|\mathcal C^*|\cdot H(\max|S|)$。

(35.12) 的证明：令 $u_i$ 为前 $i$ 步之后 $S$ 中仍未被覆盖的元素数，$u_0=|S|$。第 $i$ 步 $S$ 中有 $u_{i-1}-u_i$ 个元素首次被覆盖。贪心选的 $S_i$ 新覆盖的元素至少和 $S$ 此时能新覆盖的一样多，即 $|S_i-(S_1\cup\cdots\cup S_{i-1})|\ge u_{i-1}$。所以这些元素每个分到的代价不超过 $1/u_{i-1}$：

\sum_{x\in S}c_x\le\sum_{i}(u_{i-1}-u_i)\frac1{u_{i-1}}\le\sum_i\sum_{j=u_i+1}^{u_{i-1}}\frac1j=\sum_i\big(H(u_{i-1})-H(u_i)\big)=H(|S|).

最后一步是望远镜求和。$\square$

推导拆解：这串不等式的每一步分别在做什么。

第一个 $\le$：第 $i$ 步中 $S$ 里有 $u_{i-1}-u_i$ 个元素首次被覆盖，每个分到的代价 $\le1/u_{i-1}$，相乘再对各步求和。

第二个 $\le$：把 $(u_{i-1}-u_i)\cdot\frac1{u_{i-1}}$ 拆成 $u_{i-1}-u_i$ 个 $\frac1{u_{i-1}}$ 相加，再把每一项换成更大的 $\frac1j$，其中 $j$ 取 $u_i+1,\dots,u_{i-1}$（这些 $j$ 都不超过 $u_{i-1}$，所以 $\frac1j\ge\frac1{u_{i-1}}$）。例如 $u_{i-1}=5$、$u_i=2$ 时，$3\times\frac15\le\frac13+\frac14+\frac15$。

等号：$\sum_{j=u_i+1}^{u_{i-1}}\frac1j$ 正好是 $H(u_{i-1})-H(u_i)$。

望远镜求和：$\big(H(u_0)-H(u_1)\big)+\big(H(u_1)-H(u_2)\big)+\cdots$，中间项两两抵消，只剩 $H(u_0)-H(u_{\text{最后}})=H(|S|)-H(0)=H(|S|)$（最后 $S$ 全部被覆盖，$H(0)=0$）。名字来自老式望远镜一节节套起来、收拢后只剩首尾的样子。

直觉：$S$ 的元素被覆盖得越晚，当时 $S$ 剩下的元素越少，每个元素分摊的代价越高，最多依次是 $\frac1{|S|},\frac1{|S|-1},\dots,1$，加起来就是调和数。

推论 35.5 GREEDY-SET-COVER 是 $(\ln|X|+1)$-近似算法。

集合都很小时近似比是小常数。例如最大度不超过 3 的图上求顶点覆盖，贪心集合覆盖的近似比为 $H(3)=11/6$，略好于 2。思考题 35-3 推广到加权集合覆盖：每次选"单位新覆盖元素的权重最小"的集合，近似比仍为 $H(\max|S|)$。

35.5 随机化与线性规划

35.5.1 MAX-3-CNF 的随机 8/7-近似

随机算法的近似比用期望代价定义。MAX-3-CNF 问题：每个子句恰有三个不同文字（不含变量与其否定），求满足子句数最多的赋值。

定理 35.6 独立地以 1/2 概率把每个变量设为 0 或 1，是随机 8/7-近似算法。

证明：子句不被满足当且仅当三个文字都为 0，概率 $1/8$，所以每个子句被满足的概率是 $7/8$。由期望的线性性（附录 C），期望满足 $7m/8$ 个子句（$m$ 为子句数）。最优值至多 $m$，比值 $\le m/(7m/8)=8/7$。$\square$

白话解释：这里有两点容易困惑。第一，不同子句共用变量，它们是否被满足并不独立，但期望的线性性不要求独立：给第 $j$ 个子句定义指示变量 $Y_j$（满足为 1，否则为 0），$E[\sum_jY_j]=\sum_jE[Y_j]=m\cdot\frac78$ 总成立。第二，"期望满足 $7m/8$ 个"本身就意味着至少存在一组赋值满足不少于 $7m/8$ 个子句（一个随机变量不可能每次都低于它的均值），所以这个论证顺带证明了：任何 3-CNF 公式都至少能满足 $7/8$ 的子句。

这里的"界"是平凡的上界 $m$。同样的论证给出 MAX-CUT 的随机 2-近似（习题 35.4-3：每个顶点随机分到一侧，每条边被切的概率 1/2）。

35.5.2 LP 舍入：加权顶点覆盖

每个顶点有正权 $w(v)$，求总权最小的顶点覆盖。写成 0-1 整数规划：

\min\sum_vw(v)x(v)\quad\text{s.t. }x(u)+x(v)\ge1\ \ \forall(u,v)\in E,\quad x(v)\in\{0,1\}.

把 $x(v)\in\{0,1\}$ 放宽为 $0\le x(v)\le1$ 得到线性规划松弛（LP relaxation）。整数解都是 LP 的可行解，所以 LP 最优值 $z^*$ 是整数最优值的下界。

算法：解 LP 得 $\bar x$，取 $C=\{v:\bar x(v)\ge1/2\}$。

定理 35.7 该算法是多项式时间的 2-近似算法。

证明：每条边 $\bar x(u)+\bar x(v)\ge1$，至少一个 $\ge1/2$，所以 $C$ 是覆盖。又

z^*=\sum_vw(v)\bar x(v)\ge\sum_{v\in C}w(v)\bar x(v)\ge\frac12\sum_{v\in C}w(v)=\frac12w(C),

故 $w(C)\le2z^*\le2w(C^*)$。$\square$

金融直觉：这个方法与组合构建中的常见做法同构：先解不带整数约束的连续问题，再把结果"取整"。区别在于这里有可证明的保证。证明链 $w(C)\le2z^*\le2w(C^*)$ 中，$z^*$ 起两个作用：它是整数最优的下界（第 29 章思考题 29-3 对最大化问题给出 $IP\le P$；这里是最小化，方向反过来，$z^*\le w(C^*)$），又是舍入解的"计价基准"。

第二个不等号 $\sum_{v\in C}w(v)\bar x(v)\ge\frac12\sum_{v\in C}w(v)$ 的理由是：被选入 $C$ 的顶点 $\bar x(v)\ge\frac12$，把它们的 $\bar x(v)$ 换成 $\frac12$ 只会让和变小。直观说，LP 已经为每个入选顶点"付了至少一半的钱"，舍入成 1 最多让成本翻倍。

实务上，"整数解成本 ÷ LP 下界"就是 MILP 求解器报告的 gap 的来源。35.8.1 节的例子说明 LP 下界可能很松，所以 gap 大不一定是解差，也可能是界松。

"解 LP 松弛 → 舍入"是整数规划近似的主流方法。章末注记介绍了它的推广：随机舍入（randomized rounding，把 LP 解的分量当作概率来抽取整数解）、原始–对偶方法、半定规划（如 MAX-CUT 的 Goemans–Williamson 算法）。

35.6 子集和：完全多项式时间近似方案

优化版本：正整数集 $S=\{x_1,\dots,x_n\}$ 和上限 $t$，求不超过 $t$ 的最大子集和。原书的比喻：卡车载重上限 $t$，尽量装重。

35.6.1 指数时间的精确算法

记 $P_i$ 为 $\{x_1,\dots,x_i\}$ 所有子集和的集合，则

P_i=P_{i-1}\cup(P_{i-1}+x_i).\tag{35.23}

例：$S=\{1,4,5\}$，$P_1=\{0,1\}$，$P_2=\{0,1,4,5\}$，$P_3=\{0,1,4,5,6,9,10\}$。算法维护有序列表 $L_i$ = $P_i$ 中不超过 $t$ 的元素：每步把 $L$ 与 $L+x_i$ 归并去重，再删去超过 $t$ 的值，最后返回最大值。$|L_i|$ 可达 $2^i$，但也不超过 $t+1$，所以时间 $O(n\min(2^n,t))$——伪多项式。

35.6.2 修剪

思想：列表中两个值很接近时，只保留一个就够了，误差可控。修剪（trimming）参数 $0<\delta<1$：从 $L$ 中删除元素，使每个被删的 $y$ 都有保留的 $z$ 满足

\frac{y}{1+\delta}\le z\le y.\tag{35.24}

例：$\delta=0.1$，$L=\langle10,11,12,15,20,21,22,23,24,29\rangle$ 修剪为 $\langle10,12,15,20,23,29\rangle$（11 由 10 代表，21、22 由 20 代表，24 由 23 代表）。

def trim(L, delta):               # L 已升序
    out = [L[0]]; last = L[0]
    for y in L[1:]:
        if y > last * (1 + delta):    # last 无法代表 y，保留 y
            out.append(y); last = y
    return out

def approx_subset_sum(S, t, eps):     # 0 < eps < 1
    n = len(S); L = [0]
    for x in S:
        L = merge_lists(L, [y + x for y in L])
        L = trim(L, eps / (2 * n))
        L = [y for y in L if y <= t]
    return max(L)

原书例：$S=\langle104,102,201,101\rangle$，$t=308$，$\epsilon=0.40$，$\delta=\epsilon/8=0.05$。各步修剪并删去超过 308 的值后：$\langle0,104\rangle$；$\langle0,102,206\rangle$；$\langle0,102,201,303\rangle$；$\langle0,101,201,302\rangle$。返回 302，最优为 $307=104+102+101$，误差约 2%，远小于允许的 40%。

35.6.3 为什么是 FPTAS

定理 35.8 APPROX-SUBSET-SUM 是子集和问题的 FPTAS。

证明要点：

修剪和删除只删元素，返回值 $z^*$ 是某个子集的和，且 $z^*\le y^*$（最优值）。
归纳可证：对每个 $y\in P_i$、$y\le t$，存在 $z\in L_i$ 使 $\dfrac{y}{(1+\epsilon/2n)^i}\le z\le y$——每一轮修剪最多再丢 $(1+\epsilon/2n)$ 倍。取 $i=n$、$y=y^*$，得 $y^*/z^*\le(1+\epsilon/2n)^n$。
$(1+\epsilon/2n)^n$ 随 $n$ 单调增，极限是 $e^{\epsilon/2}$，所以 $\left(1+\frac{\epsilon}{2n}\right)^n\le e^{\epsilon/2}\le1+\frac\epsilon2+\left(\frac\epsilon2\right)^2\le1+\epsilon.\tag{35.30}$
列表长度：修剪后相邻元素之比大于 $1+\epsilon/2n$，所以列表长度至多 $\log_{1+\epsilon/2n}t+2=\frac{\ln t}{\ln(1+\epsilon/2n)}+2<\frac{3n\ln t}{\epsilon}+2,$ （用 $\ln(1+x)\ge x/(1+x)$。）它关于 $n$、$\lg t$（$t$ 的位数）和 $1/\epsilon$ 都是多项式。

总时间 $O(n^2\ln t/\epsilon)$。$\square$

推导拆解：第 2–3 步的逻辑是"每轮丢一点，$n$ 轮共丢多少"。每轮修剪最多让结果缩小到原来的 $\frac1{1+\delta}$（$\delta=\epsilon/2n$），$n$ 轮叠加就是 $\frac1{(1+\delta)^n}$，和复利完全一样：每期"折损率" $\delta$，$n$ 期累计折损 $(1+\delta)^n$ 倍。

第 3 步的三个不等号：第一个用了"$(1+x/n)^n$ 随 $n$ 增大而增大、极限为 $e^x$"（这里 $x=\epsilon/2$），即离散复利不超过连续复利；第二个是 $e^y$ 的泰勒展开 $1+y+\frac{y^2}{2}+\frac{y^3}{6}+\cdots$ 在 $0<y\le\frac12$ 时不超过 $1+y+y^2$（后面各项之和不超过 $\frac{y^2}2$）；第三个只需 $(\epsilon/2)^2\le\epsilon/2$，在 $\epsilon<1$ 时成立。

第 4 步：修剪后相邻两个保留值之比都大于 $1+\delta$，所以从 1 到 $t$ 最多能放下 $\log_{1+\delta}t$ 个值，就像价格以固定百分比为刻度时，从 1 元到 $t$ 元的刻度数只与 $\ln t$ 成正比。

修剪的本质是：把"绝对数值"的状态空间（大小 $t$）换成"相对精度"的状态空间（大小约 $\ln t/\delta$，按对数刻度分桶）。这一思想在量化里很有用：凡是"状态是金额、只关心相对误差"的动态规划，都可以这样压缩状态数。

35.7 思考题选讲

装箱（bin packing，思考题 35-1）：$n$ 个大小在 $(0,1)$ 的物体装入最少的单位容量箱。NP 难（从子集和归约）。首次适配（first-fit）至多让一个箱子不足半满，所以用箱数 $\le\lceil2S\rceil$（$S$ 为总大小），而最优至少 $\lceil S\rceil$，故为 2-近似；用平衡树维护剩余容量可做到 $O(n\lg n)$。
最大团（35-2）：利用图的 $k$ 次"幂" $G^{(k)}$，最大团规模变成 $k$ 次方。若有常数近似，就能把比值开 $k$ 次根而得到 PTAS——这是"近似比放大"技巧。
极大匹配（35-4）：贪心求极大匹配是最大匹配的 2-近似，线性时间；其端点集合是一个顶点覆盖。
并行机调度（35-5）：$n$ 个作业、$m$ 台相同机器，最小化完工时间跨度（makespan）$C_{\max}$。两个下界：$C^*_{\max}\ge\max_kp_k$，$C^*_{\max}\ge\frac1m\sum_kp_k$。列表调度贪心（有机器空闲就分配任一未调度作业）满足 $C_{\max}\le\frac1m\sum_kp_k+\max_kp_k$，因此是 2-近似；用优先队列实现 $O(n\lg m)$。原书例：两台机器，$p=(2,12,4,5)$，一种贪心调度 $C_{\max}=14$，最优为 12。这是历史上第一个被分析的近似算法（Graham）。
最大生成树（35-6）：每个顶点取其最大权的关联边，所得边集权重至少是最大生成树的一半，$O(V+E)$。
0-1 背包的 2-近似（35-7）：物品按价值降序编号。对每个 $j$，考虑受限实例 $I_j$：去掉物品 $1..j-1$，必须选物品 $j$。先放 $j$，再按单位重量价值贪心装填，装到第一个放不下的物品就停（分数背包会部分装入它，这里直接丢弃），得到 $R_j$。被丢弃的物品价值不超过 $v_j$，而 $v_j$ 已在解中，所以 $v(R_j)\ge\frac12v(Q_j)\ge\frac12v(P_j)$（$Q_j$、$P_j$ 分别是分数与 0-1 最优），取 $R_1,\dots,R_n$ 中最好的就是 2-近似。

35.8 量化实战

35.8.1 顶点覆盖：下界与 LP 舍入的实际表现

先在随机图上看两种 2-近似算法的实际比值，并用 scipy.optimize.milp 求出精确最优作对照。

import numpy as np
from scipy.optimize import milp, linprog, LinearConstraint, Bounds

rng = np.random.default_rng(2)
n = 40
edges = [(u, v) for u in range(n) for v in range(u + 1, n) if rng.random() < 0.15]
w = rng.uniform(1, 10, n)                                     # 顶点权重

def approx_vertex_cover(edges):
    C = set()
    for u, v in edges:
        if u not in C and v not in C:
            C |= {u, v}
    return C

A = np.zeros((len(edges), n))
for r, (u, v) in enumerate(edges):
    A[r, u] = A[r, v] = 1
cons = LinearConstraint(A, lb=1, ub=np.inf)                   # x_u + x_v >= 1
exact_unw = milp(np.ones(n), constraints=cons, integrality=np.ones(n), bounds=Bounds(0, 1))
C = approx_vertex_cover(edges)
print(f"{n} 顶点 {len(edges)} 条边：APPROX-VERTEX-COVER 得 {len(C)} 个顶点，最优 {exact_unw.fun:.0f}，比值 {len(C) / exact_unw.fun:.2f}")

lp = linprog(w, A_ub=-A, b_ub=-np.ones(len(edges)), bounds=[(0, 1)] * n)   # LP 松弛
C_lp = {v for v in range(n) if lp.x[v] >= 0.5}                             # 1/2 阈值舍入
exact_w = milp(w, constraints=cons, integrality=np.ones(n), bounds=Bounds(0, 1))
assert all(u in C_lp or v in C_lp for u, v in edges)
print(f"LP 最优解中取值为 1/2 的变量 {np.sum(np.isclose(lp.x, 0.5))} 个")
print(f"加权：LP 下界 {lp.fun:.2f}，舍入解 {w[list(C_lp)].sum():.2f}，整数最优 {exact_w.fun:.2f}，"
      f"比值 {w[list(C_lp)].sum() / exact_w.fun:.3f}（保证 <= 2）")

输出：

40 顶点 111 条边：APPROX-VERTEX-COVER 得 34 个顶点，最优 24，比值 1.42
LP 最优解中取值为 1/2 的变量 40 个
加权：LP 下界 114.85，舍入解 229.70，整数最优 133.09，比值 1.726（保证 <= 2）

这个例子很有教育意义：LP 松弛的最优解把所有变量都取成 1/2（顶点覆盖 LP 的最优解总可以取成只含 0、1/2、1 的"半整数"解），舍入后选中了全部顶点，舍入解恰好是 LP 下界的 2 倍。对照整数最优，实际比值 1.73，仍在保证之内，但离最优不近。教训有两条：一是 LP 下界本身可能很松（114.85 对 133.09），用它评估启发式解时，"离下界还差 X%"只是上界意义下的差距；二是生产中 LP 舍入通常只是起点，后面要接局部改进（删掉冗余顶点）或交给 MILP 求解器。

35.8.2 集合覆盖：选最少的对冲工具

设组合有 60 类需要对冲的风险暴露（行业 × 风格等），市场上有 40 种可用的对冲工具（行业 ETF、股指期货、风格指数期货等），每种工具能覆盖其中若干类。为了降低管理成本和保证金占用，希望用最少的工具覆盖全部暴露。这就是集合覆盖。

import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds

rng = np.random.default_rng(8)
n_exp, n_inst = 60, 40
cover = [set(rng.choice(n_exp, rng.integers(3, 12), replace=False)) for _ in range(n_inst)]
for e in set(range(n_exp)) - set().union(*cover):   # 保证每个暴露至少能被一个工具覆盖
    cover[rng.integers(n_inst)].add(e)

def greedy_set_cover(X, F):
    U, C = set(X), []
    while U:
        i = max(range(len(F)), key=lambda i: len(F[i] & U))
        U -= F[i]; C.append(i)
    return C

C = greedy_set_cover(range(n_exp), cover)
M = np.zeros((n_exp, n_inst))
for i, S in enumerate(cover):
    M[list(S), i] = 1
opt = milp(np.ones(n_inst), constraints=LinearConstraint(M, lb=1, ub=np.inf),
           integrality=np.ones(n_inst), bounds=Bounds(0, 1))
H = sum(1 / i for i in range(1, max(len(S) for S in cover) + 1))
print(f"贪心选 {len(C)} 个工具，整数规划最优 {opt.fun:.0f} 个；理论保证 <= H(max|S|) = {H:.2f} 倍")

输出：

贪心选 13 个工具，整数规划最优 12 个；理论保证 <= H(max|S|) = 3.02 倍

贪心只比最优多一个工具，远好于理论上界 3.02 倍。这类问题规模不大时直接用 MILP 求解器就能求到最优；贪心的价值在于规模很大（例如从几千个数据字段里选最少的数据源覆盖全部所需字段）或需要可解释的逐步决策时。真实场景通常要用加权版本（每个工具有成本：手续费、流动性、基差风险），按"单位新覆盖暴露的成本最小"贪心，保证不变（思考题 35-3）。

35.8.3 子集和 FPTAS：按整笔订单凑目标金额

设有 40 笔可选的整笔订单（大宗交易、ETF 申赎篮子、按整手的订单），每笔金额已定，要选一批使总金额尽量接近但不超过目标 3000 万元。精确的列表算法状态数会膨胀到数百万；FPTAS 用修剪把状态数控制在 $O(n\ln t/\epsilon)$。

import numpy as np, time

def merge_lists(L1, L2):                      # 有序归并并去重
    out, i, j = [], 0, 0
    while i < len(L1) or j < len(L2):
        if j == len(L2) or (i < len(L1) and L1[i] < L2[j]): x = L1[i]; i += 1
        else: x = L2[j]; j += 1
        if not out or out[-1] != x: out.append(x)
    return out

def trim(L, delta):
    out = [L[0]]; last = L[0]
    for y in L[1:]:
        if y > last * (1 + delta):
            out.append(y); last = y
    return out

def approx_subset_sum(S, t, eps, verbose=False):
    n = len(S); L = [0]; max_len = 1
    for x in S:
        L = merge_lists(L, [y + x for y in L])
        L = trim(L, eps / (2 * n))
        L = [y for y in L if y <= t]
        max_len = max(max_len, len(L))
        if verbose: print("   ", L)
    return max(L), max_len

def exact_subset_sum(S, t):
    L = [0]; max_len = 1
    for x in S:
        L = [y for y in merge_lists(L, [y + x for y in L]) if y <= t]
        max_len = max(max_len, len(L))
    return max(L), max_len

print("原书例：S=<104,102,201,101>, t=308, eps=0.4")
z, _ = approx_subset_sum([104, 102, 201, 101], 308, 0.40, verbose=True)
print("  近似解", z, "；精确解", exact_subset_sum([104, 102, 201, 101], 308)[0])

rng = np.random.default_rng(4)
orders = [int(x) for x in rng.integers(50_000, 5_000_000, 40)]
t = 30_000_000
t0 = time.perf_counter(); z_ex, len_ex = exact_subset_sum(orders[:24], t); dt_ex = time.perf_counter() - t0
print(f"精确算法（只用前 24 笔）：{z_ex:,}，列表最长 {len_ex:,}，用时 {dt_ex:.2f}s")
for eps in (0.1, 0.01, 0.001):
    t0 = time.perf_counter(); z, L = approx_subset_sum(orders, t, eps); dt = time.perf_counter() - t0
    print(f"FPTAS 全部 40 笔, eps={eps:<6}: {z:,}（缺口 {(t - z) / t:.5%}），列表最长 {L}，用时 {dt:.3f}s")

输出：

原书例：S=<104,102,201,101>, t=308, eps=0.4
    [0, 104]
    [0, 102, 206]
    [0, 102, 201, 303]
    [0, 101, 201, 302]
  近似解 302 ；精确解 307
精确算法（只用前 24 笔）：30,000,000，列表最长 3,409,937，用时 1.06s
FPTAS 全部 40 笔, eps=0.1   : 29,973,587（缺口 0.08804%），列表最长 1524，用时 0.011s
FPTAS 全部 40 笔, eps=0.01  : 29,998,370（缺口 0.00543%），列表最长 12028，用时 0.071s
FPTAS 全部 40 笔, eps=0.001 : 29,999,712（缺口 0.00096%），列表最长 94436，用时 0.548s

解读：

第一段逐步复现了原书的列表，结果 302 与原书一致。
精确算法只用 24 笔订单，列表就涨到 340 万项；40 笔时状态数会逼近 $t=3\times10^7$，Python 列表难以承受。
FPTAS 的列表长度和用时随 $1/\epsilon$ 大致线性增长，与理论 $O(n\ln t/\epsilon)$ 一致；实际缺口比保证的 $\epsilon$ 小两个数量级——再次说明近似比是最坏情况界。实际系统里还要让算法返回所选子集（习题 35.5-5：保存回溯指针）。

35.8.4 背包与调度：资金分配和回测任务分配

资金约束下选择交易机会。每个机会占用资金 $w_i$、预期收益 $v_i$，总资金 $W$，选一批使预期收益最大——0-1 背包。最常见的做法是"按收益率（$v_i/w_i$）从高到低装，装不下就停"，但它没有任何近似保证。思考题 35-7 的算法只多了一层循环，就有 2-近似保证。

回测任务调度。参数扫描、多股票回测会产生大量耗时不一的任务，分配给 $m$ 个进程，目标是总完工时间最短——这正是思考题 35-5 的并行机调度。

import numpy as np, heapq
from scipy.optimize import milp, LinearConstraint, Bounds

def knapsack_2approx(v, w, W):
    order = np.argsort(-v)                         # 按价值降序编号 1..n
    v, w = v[order], w[order]
    best_val, best_set = 0.0, []
    for j in range(len(v)):                        # 受限实例 I_j：删去 1..j-1，必须含 j
        if w[j] > W: continue
        cap, chosen, val = W - w[j], [j], v[j]
        rest = [i for i in range(j + 1, len(v))]
        rest.sort(key=lambda i: -v[i] / w[i])      # 按单位资金收益贪心装填
        for i in rest:
            if w[i] <= cap:
                cap -= w[i]; chosen.append(i); val += v[i]
            else:
                break                              # 分数背包会部分装入此物品；R_j 直接丢弃它
        if val > best_val:
            best_val, best_set = val, [order[i] for i in chosen]
    return best_val, best_set

rng = np.random.default_rng(6)
n = 60
cap_used = rng.uniform(1, 20, n)                   # 每个机会占用的资金（百万元）
exp_pnl = cap_used * rng.uniform(0.0, 0.08, n) + rng.exponential(0.2, n)   # 预期收益
W = 120.0
val, S = knapsack_2approx(exp_pnl, cap_used, W)
opt = milp(-exp_pnl, constraints=LinearConstraint(cap_used[None, :], ub=W),
           integrality=np.ones(n), bounds=Bounds(0, 1))
dens = np.argsort(-exp_pnl / cap_used)             # 朴素"按收益率贪心"，装不下就停
naive = 0.0; c = 0.0
for i in dens:
    if c + cap_used[i] > W: break
    c += cap_used[i]; naive += exp_pnl[i]
print(f"最优 {-opt.fun:.3f}，思考题 35-7 近似 {val:.3f}（比值 {-opt.fun / val:.3f}），朴素收益率贪心 {naive:.3f}")
# 朴素贪心的病态例子：小机会收益率高，大机会收益率低但几乎占满资金
v_bad, w_bad = np.array([2.0, 100.0]), np.array([1.0, 100.0])
print("病态例：朴素收益率贪心只拿到 2.0；35-7 近似", knapsack_2approx(v_bad, w_bad, 100.0)[0], "；最优 100.0")

def list_scheduling(p, m):
    heap = [(0.0, k) for k in range(m)]            # (当前完工时间, 机器号)
    for x in p:
        load, k = heapq.heappop(heap)              # 交给最早空闲的机器
        heapq.heappush(heap, (load + x, k))
    return max(load for load, _ in heap)

jobs = rng.lognormal(1.0, 1.0, 200)                # 200 个回测任务的耗时（分钟），重尾
m = 16
lb = max(jobs.max(), jobs.sum() / m)               # 最优 makespan 的下界
ls = list_scheduling(jobs, m)
lpt = list_scheduling(np.sort(jobs)[::-1], m)      # 先排长任务（LPT）
print(f"下界 {lb:.1f}，到达顺序贪心 {ls:.1f}（<= {ls / lb:.3f} 倍最优），LPT {lpt:.1f}（<= {lpt / lb:.3f} 倍最优）")

输出：

最优 13.302，思考题 35-7 近似 12.690（比值 1.048），朴素收益率贪心 12.690
病态例：朴素收益率贪心只拿到 2.0；35-7 近似 100.0 ；最优 100.0
下界 53.8，到达顺序贪心 71.2（<= 1.323 倍最优），LPT 54.0（<= 1.004 倍最优）

解读：

在"正常"的随机实例上，35-7 近似和朴素收益率贪心结果相同，离最优约 5%。但病态例说明朴素贪心可以任意差（拿 2 而最优是 100）：一个收益率稍高的小机会挤掉了几乎占满资金的大机会。35-7 的算法通过"枚举必选的高价值物品"堵住了这个漏洞。机会数在几百以内时，直接用 MILP 求解器或以"万元"为单位的 $O(nW)$ 动态规划求最优更好；近似算法的价值在于有保证、可解释、极快。
调度结果的比值是相对下界算的，所以是实际比值的上界。到达顺序的贪心离下界 32%，而"先排长任务"（LPT，longest processing time first）几乎贴着下界——重尾的任务耗时下，最后才分配一个超长任务是贪心变差的主要原因。LPT 有更好的理论保证（Graham 证明为 $\frac43-\frac1{3m}$），实践中几乎总应该先按预估耗时降序排列任务。

35.8.5 小结：评估启发式的三件工具

本章的量化落点可以归结为三条：

先判断难度（第 34 章）：问题能否写成凸优化？若含离散决策，多半 NP 难。
有界才能评估：给启发式解配一个可计算的最优值界——LP/QP 松弛、对偶、简单的计数下界（如调度中的 $\max(\max p,\sum p/m)$）。"解 ÷ 界"给出离最优的差距上界；MILP 求解器报告的 MIP gap 就是这个思想。
最坏保证与平均表现分开看：近似比是最坏情况保证，实际表现通常好得多；反过来，没有保证的贪心（如朴素收益率贪心）可能在特定结构上崩溃，要用病态例子测试。

本章小结

近似算法在多项式时间内给出有保证的近似最优解，近似比定义为 $\max(C/C^*,C^*/C)$；PTAS 对每个固定 $\epsilon$ 是多项式，FPTAS 对 $1/\epsilon$ 也是多项式。证明近似比的通用方法是找到最优值的可计算界：极大匹配（顶点覆盖 2-近似）、最小生成树（三角不等式 TSP 2-近似）、代价分摊与调和数（集合覆盖 $H(\max|S|)\le\ln|X|+1$）、全部子句数与期望线性性（MAX-3-CNF 随机 8/7）、LP 松弛（加权顶点覆盖 2-近似）。一般 TSP 由间隙归约证明不可常数近似。子集和的 FPTAS 用修剪把列表长度控制在 $O(n\ln t/\epsilon)$，总时间 $O(n^2\ln t/\epsilon)$。在量化里，这些结果用于对冲工具选择、订单凑整、资金约束下的机会选择和计算任务调度；更重要的是"用下界评估启发式"的思维方式。

问题	算法	近似比	关键下界 / 工具	时间
顶点覆盖	选边取两端点	2	极大匹配	$O(V+E)$
TSP（三角不等式）	MST + 前序遍历	2	$c(T)\le c(H^*)$	$\Theta(V^2)$
一般 TSP	—	无常数近似（P≠NP）	间隙归约	—
集合覆盖	贪心	$H(\max\lvert S\rvert)\le\ln\lvert X\rvert+1$	代价分摊	多项式
MAX-3-CNF	随机赋值	8/7（期望）	上界 $m$，期望线性性	$O(n+m)$
加权顶点覆盖	LP 松弛 + 1/2 舍入	2	LP 最优值	LP 时间
子集和	列表 + 修剪	$1+\epsilon$（FPTAS）	相对误差逐轮累积	$O(n^2\ln t/\epsilon)$
装箱	首次适配	2	$\lceil\sum s_i\rceil$	$O(n\lg n)$
并行机调度	列表调度	2	$\max(\max p,\sum p/m)$	$O(n\lg m)$
0-1 背包	思考题 35-7	2	分数背包	多项式

练习

基础

给出一个图，使 APPROX-VERTEX-COVER 总是得到次优解。（原书 35.1-1。提示：一条边连接两个顶点，最优为 1、算法为 2。）
证明 APPROX-VERTEX-COVER 选中的边集是一个极大匹配。（原书 35.1-2。）
设计树上求最优顶点覆盖的线性时间贪心算法。（原书 35.1-4。提示：叶子的父结点总可以放进覆盖。）
对单词集合 {arid, dash, drain, heard, lost, nose, shun, slate, snare, thread}，以字母为元素，手算 GREEDY-SET-COVER（平局取字典序靠前的单词）。（原书 35.3-1。）
证明 MAX-CUT 的随机算法（每个顶点独立地以 1/2 概率放入 $S$）是随机 2-近似。（原书 35.4-3。）
用 35.6.2 节的修剪规则，对 $L=\langle10,11,12,15,20,21,22,23,24,29\rangle$、$\delta=0.1$ 手算修剪结果并与原书核对。
两台机器、作业耗时 $(2,12,4,5)$，写出一个 $C_{\max}=14$ 的列表调度顺序，以及最优调度。（原书思考题 35-5 的例子。）

进阶

用归纳法证明式 (35.26)：对每个 $y\in P_i$、$y\le t$，存在 $z\in L_i$ 使 $y/(1+\epsilon/2n)^i\le z\le y$。（原书 35.5-2。）
修改 APPROX-SUBSET-SUM，使它同时返回取到 $z^*$ 的子集。（原书 35.5-5。提示：列表元素带回溯指针。）
说明为什么"给每条边加一个大常数"把一般 TSP 变成满足三角不等式的 TSP，最优巡回不变，却不与定理 35.3 矛盾。（原书 35.2-2。）
证明首次适配装箱用箱数 $\le\lceil2S\rceil$。（原书思考题 35-1(c)(d)。）
证明列表调度满足 $C_{\max}\le\frac1m\sum_kp_k+\max_kp_k$。在 35.8.4 节的代码里构造一组任务，使"到达顺序贪心"的比值接近 2（提示：$m(m-1)$ 个耗时 1 的任务之后跟一个耗时 $m$ 的任务）。
把 35.8.2 节改为加权集合覆盖：每个工具有成本 $c_i$，实现"单位新覆盖暴露成本最小"的贪心，并与 MILP 最优比较。（原书思考题 35-3。）
对 35.8.1 节的加权顶点覆盖，在舍入之后加一步"删去冗余顶点"（若删除某顶点后仍是覆盖就删除，按权重从大到小尝试），观察比值的改进。

原书推荐习题：35.1-2，35.2-2，35.3-3，35.4-3，35.5-2，35.5-5，思考题 35-1、35-5、35-7。

原书对照

本章小节	原书章节	PDF 页码
35.1 近似比与近似方案	第 35 章导言	p.1127–1129
35.2 顶点覆盖	35.1 The vertex-cover problem	p.1129–1132
35.3 旅行商问题	35.2 The traveling-salesman problem	p.1131–1138
35.4 集合覆盖	35.3 The set-covering problem	p.1137–1143
35.5 随机化与线性规划	35.4 Randomization and linear programming	p.1144–1149
35.6 子集和 FPTAS	35.5 The subset-sum problem	p.1149–1155
35.7 思考题选讲	Problems 35-1 ～ 35-7，Chapter notes	p.1155–1161

第 35 章 近似算法