最大覆盖问题

最大覆盖问题（maximum coverage problem）是在给定集合族中最多选择 $k$ 个集合，使它们覆盖的不同对象尽可能多。一个对象被多个所选集合包含时只计算一次。常见模型包括在固定站点数下覆盖尽可能多的需求点，以及在有限试验预算下覆盖尽可能多的目标情形。

设八个教学需求点编号为一到八，候选方案覆盖 $$A=\{1,2,3,4,5\},B=\{1,2,6,7\},C=\{3,4,5,8\}.$$ 若只能选两个，先选覆盖最多的 $A$ 看似合理，随后加入 $B$ 只能覆盖七点；直接选 $B,C$ 却能覆盖全部八点。这是贪心有保证但未必最优的一个小例子。

数学模型与边际增量

设有限对象集为 $U$，候选集合为 $C_1,\dots ,C_m\subseteq U$，预算 $k\in \{0,\dots ,m\}$。对所选指标集 $S\subseteq \{1,\dots ,m\}$，定义 $$f(S)=\left|\bigcup _{j\in S}{C}_j\right|,\underset{|S|\le k}{max}f(S).$$ 空并集取空集，故 $f(\varnothing )=0$。新增候选 $j\notin S$ 的边际为 $${\Delta }_j(S)=|C_j\setminus \bigcup _{i\in S}{C}_i|.$$ 它统计尚未被覆盖的对象，不能直接用 $|C_j|$ 代替。随着 $S$ 扩大，已经覆盖的集合扩大，差集只能缩小，因此 $f$ 是单调次模函数。

也可给对象非负权重 $w_u$，将基数换成被覆盖对象的权重和，仍有同样的边际递减。但候选集合的成本若不同，约束会由基数变成预算和，下面这套“每轮选一个”的分析不能不加修改地搬过去。

不同集合中的同一列仍是同一个需求点。重叠的覆盖不重复计分。

贪心过程与可复算反例

从空集出发，每一轮加入一个边际增量最大的未选候选，直到选满 $k$ 个，或没有正增量为止。

在开头例子中，第一轮增量为 $5,4,4$，唯一选择 $A$。第二轮 $B$ 的新覆盖是 $\{6,7\}$，增量二；$C$ 的新覆盖只有 $\{8\}$，增量一，故贪心选 $A,B$，覆盖七点。枚举另两对得 $$f(\{A,C\})=6,f(\{B,C\})=8.$$ 因此最优值八、贪心值七。这个反例不依赖平局处理；第一轮和第二轮都是严格较大增量。

金色标出第二轮的新覆盖，不是候选集合的全部大小。选择最大的原集合与每轮选择最大的新增覆盖是不同规则。

近似保证的完整证明

对 $k\ge 1$，记最优值为 $\mathrm{O}\mathrm{P}\mathrm{T}$，贪心选完 $i$ 轮的集合为 $S_i$。选取某个最优指标集 $O$，其中最多含 $k$ 个候选。尚未被 $S_i$ 覆盖、但被 $O$ 覆盖的对象，至少有 $\mathrm{O}\mathrm{P}\mathrm{T}-f(S_i)$ 个。

依次加入 $O\setminus S_i$ 的候选时，每个对象至少会被某个候选新覆盖一次；而在较小背景 $S_i$ 下计算的单个边际，不小于在逐步扩大背景下的边际。因此 $$\sum _{j\in O\setminus S_i}{\Delta }_j(S_i)\ge f(S_i\cup O)-f(S_i)\ge \mathrm{O}\mathrm{P}\mathrm{T}-f(S_i).$$ 至多 $k$ 项中至少一项不小于剩余差距的 $1/k$，贪心选择的增量还不会更小。于是 $$\mathrm{O}\mathrm{P}\mathrm{T}-f(S_{i+1})\le (1-\frac{1}{k})[\mathrm{O}\mathrm{P}\mathrm{T}-f(S_i)].$$ 初始值为零，重复 $k$ 轮得到 $$f(S_k)\ge [1-{(1-\frac{1}{k})}^k]\mathrm{O}\mathrm{P}\mathrm{T}\ge (1-e^{-1})\mathrm{O}\mathrm{P}\mathrm{T}.$$ 若提前没有正增量，所有候选的并集已经被当前集合覆盖，实际上已达到最优值。预算二时较精细的保证是 $3/4$，本例的 $7/8$ 高于它。

证明中的单调性、非负对象权重和基数预算都有作用。比如允许对象贡献负分，新增覆盖就可能降低目标；若候选有不同成本，也不能再由“最优最多含 $k$ 项”这一步得到原来的相同结论。

Python 实现

输入为有限集合族和非负整数预算，返回候选的输入索引及覆盖到的集合，不改写输入。平局取输入位置靠前的候选。

Python 3

def greedy_maximum_coverage(sets, budget):
    if type(budget) is not int or budget < 0:
        raise ValueError("budget must be a nonnegative integer")
    groups = tuple(frozenset(group) for group in sets)
    chosen, covered = [], set()
    remaining = set(range(len(groups)))
    for _ in range(min(budget, len(groups))):
        best = max(remaining, key=lambda j: (len(groups[j] - covered), -j))
        if not groups[best] - covered:
            break
        chosen.append(best)
        covered.update(groups[best])
        remaining.remove(best)
    return chosen, covered


groups = [{1, 2, 3, 4, 5}, {1, 2, 6, 7}, {3, 4, 5, 8}]
chosen, covered = greedy_maximum_coverage(groups, 2)
print(chosen, sorted(covered))
# [0, 1] [1, 2, 3, 4, 5, 6, 7]

每一轮 covered 恰为已经选择的集合之并，remaining 恰含未选索引；取差集和更新并集维持这个不变量。因此程序实现的确是逐轮最大边际规则。设总输入成员数为 $L=\sum _j|C_j|$，按散列表平均成本计，朴素扫描需 $O((k+1)(m+L))$ 时间和 $O(m+L)$ 额外空间；候选很多时可以缓存边际并利用次模上界加速，但需相应的更新论证。

变式。 预算为一时选 $A$、值五，已经最优；预算三时再加入 $C$，覆盖全部八点；预算零返回空选择与空覆盖。空候选、重复候选不会破坏算法，但不会凭空增加覆盖对象。

最大覆盖固定可选数量并最大化覆盖；集合覆盖要求覆盖全部对象并最小化所选数量，击中集则用点去命中给定集合。它们有关联，却有不同的目标、约束及保证，不能混用同一个贪心比例。