第30篇的集合覆盖要求覆盖全部目标，尽量降低成本。本篇改变约束：最多选择k个集合，尽量覆盖更多元素。两个问题都可能每轮挑选新增覆盖多的集合，但目标函数、停止条件和近似比不同，不能直接互换证明。

最大覆盖是单调次模最大化的一个实例。它适合完整展示贪心保证：每一步至少消除剩余最优差距的1/k，而这个结论同时依赖预算、单调性与边际递减。

元素宇宙与候选集合

元素宇宙为整数0到U−1，U≥0。输入有n个候选集合C_0到C_{n−1}，每个元素必须在宇宙内；不同ID可以具有相同集合内容。预算k是非负整数，输出至多k个不同候选ID以及它们的并集。

令S为选中的候选ID集合，目标函数f(S)是其覆盖元素数。候选ID与被覆盖元素属于两种对象，不能把“选了三个集合”和“覆盖了三个元素”混用。

空候选族或k=0返回空选择与空覆盖。U=0时所有合法候选均为空，最优值也是0。预算超过候选数量不需要重复选择同一ID；最多考虑全部n个候选。

从新增覆盖看次模性

函数归一化意味着f(空集)=0。单调性意味着S包含于T时f(S)≤f(T)。加入更多候选不会删除已覆盖元素，所以最大覆盖满足两者。

把新增候选x的边际贡献记为Δ(x|S)=f(S∪{x})−f(S)。次模性可写成：当S包含于T且x不在T中，Δ(x|S)≥Δ(x|T)。在覆盖问题中，边际就是C_x里尚未被选中集合覆盖的元素数。T覆盖更多，剩下可新增的元素只能减少，因此满足边际递减。

贪心从空集开始，每轮选择未选候选中边际最大的一个，并列时选择较小ID。若最大边际为0，所有剩余集合都不含未覆盖元素，其任意组合也不能扩大并集，可以提前停止。这个停止判断利用了覆盖语义，不是“任何目标函数单步没有收益就已经最优”。

实现每轮从当前并集重新计算边际，没有缓存已经过期的新增覆盖数。否则前一轮选中集合后，另一个候选与它的重叠会使真实收益下降，旧排序不能继续当作当前最大边际。

剩余差距怎样收缩

先设1≤k≤n，O是大小至多k的最优选择，最优值记为OPT。第i轮后的贪心集合记为S_i。由单调性，f(O)≤f(S_i∪O)，因此

OPT−f(Si)≤f(Si∪O)−f(Si).OPT-f(S_i)\le f(S_i\cup O)-f(S_i).

把O中还未选的候选逐个加入S_i。实际后续边际受到先加入元素的影响；次模性保证，每一项不超过它直接加入S_i时的边际。于是

f(Si∪O)−f(Si)≤∑x∈O∖SiΔ(x∣Si).f(S_i\cup O)-f(S_i) \le \sum_{x\in O\setminus S_i}\Delta(x\mid S_i).

求和至多k项，每项不超过贪心下一步选出的最大边际，得到

OPT−f(Si)≤k [f(Si+1)−f(Si)].OPT-f(S_i)\le k\,[f(S_{i+1})-f(S_i)].

令g_i=OPT−f(S_i)，移项得到g_{i+1}≤(1−1/k)g_i。归一化给g_0=OPT，迭代k次后

f(Sk)≥[1−(1−1/k)k]OPT≥(1−1/e)OPT.f(S_k)\ge [1-(1-1/k)^k]OPT\ge(1-1/e)OPT.

最后一步用1−x≤e^{−x}。这里的保证是每个合法输入上的确定性近似比，不是期望值或高概率界，也没有隐藏随机舍入步骤。

若提前停止，当前覆盖已经等于所有候选的总并集，因而达到最优，保证仍成立。k=0需单独处理，不能把0代入1/k。k≥n时选择全部可达到最优，提前停止只省去没有新增贡献的候选。

有保证仍可能不是最优

设A={0,1,2,3}，B={0,1,4}，C={2,3,5}，预算k=2。贪心先选覆盖4个元素的A，再选B或C，只覆盖5个；最优选择B与C覆盖6个。

所得比值5/6满足保证，但它证明贪心不能被描述成精确算法。这里的近似比下界是“所得值至少为最优值的多少”，与最小化问题中“成本至多最优值的多少”方向不同。

去掉单调性，哪一步断裂

考虑两个顶点a、b之间一条无向边，f(S)为跨越S与补集的边数。四个函数值为f(空集)=0、f({a})=f({b})=1、f({a,b})=0。它非负且归一化，也满足次模性；唯一真正互不包含的两个非空集合给出1+1≥0+0，其余包含情形取等或直接满足。

这个函数不单调。若把贪心改成无论边际正负都强制选满k=2，第一步得到1，第二步反而回到0，而“至多2个”的最优值为1。证明中的f(O)≤f(S_i∪O)此时不再成立。

反例针对强制选满的非单调推广。它不是本文最大覆盖实现的失败输入，也没有证明所有会在负边际时停止的算法都失败。条件改变后，应重新分析对应变体，而不是沿用原近似比。

实现成本与复跑范围

教学实现位于examples/advanced-algorithms/maximum_coverage.py。每轮扫描全部候选，用集合差计算新增元素数。已选候选的增益必为0，因此即使扫描到它，也不会再次选中；严格大于才更新最佳候选，使相同正增益按较小ID决定。

令k′=min(k,n)。在元素编号能放入机器字、散列表基本操作取期望常数成本的模型下，包含输入范围检查的宽松时间上界为O(1+(k′+1)n(U+1))。最多保存覆盖并集、临时集合差和选中ID，额外空间为O(U+k′+1)，不计调用者持有的候选集合。Python大整数的位运算与哈希成本需另计。这里的期望来自散列表成本模型；贪心近似保证本身仍是确定性的，不能把两种结论混为一谈。

在仓库根目录运行：

1
python3 examples/advanced-algorithms/check_maximum_coverage.py

独立参照枚举大小至多k的候选ID组合，直接计算并集并寻找最优值，不调用贪心选择逻辑。本次实际运行覆盖585个有序集合族、2842个预算实例、100个固定种子随机实例，以及空宇宙、空候选族、重复内容与非法范围等边界。检查用Fraction精确比较1−(1−1/k)^k，避免浮点误差影响断言。

固定例子实际得到贪心值5、最优值6。两点割函数的16对集合次模不等式也通过检查，强制取满得到0、至多预算最优为1。原始结果保存在writing-plans/advanced-algorithms/evidence/maximum-coverage-results.json。这些是有限实例上的教学实现检查；一般近似保证依赖前面的证明，没有进行大规模性能测量。

练习

  1. 在A、B、C的例子中，逐轮写出所有剩余边际。说明第1轮的最大覆盖数为什么不能保证最终选择最优，并核对k=2时的有理保证系数。
  2. 把割函数例子的预算改成k=1，再改回k=2但遇到负边际就停止。分别计算结果，并指出原反例究竟否定了哪一种推广。

参考资料

  • Cornell CS6820：Submodular Functions：第1页边际递减，第2页覆盖函数，第3页割函数，第8页Theorem 4的单调次模贪心保证。本文逐步写出不等式链，并单列零预算与失去单调性的边界。