“安排合适的人完成任务”和“用最低成本覆盖全部目标”都包含选择，但它们选择的对象、限制和目标不同。二分图匹配的最优证书，不能替一个集合覆盖方案证明成本最优；覆盖了所有目标，也不代表有足够人员执行选中的方案。

本篇复用27篇的二分图匹配和30篇的加权集合覆盖贪心。两种输出分别验收，只有明确增加联合模型后，才能讨论联合方案的可行性与最优性。

资格分配：每个人和任务最多出现一次

输入是a名人员、b个任务，以及m条资格边。边(u,v)表示人员u可以执行任务v，左右编号属于两个独立集合。每个人至多承担一个任务，每个任务至多由一人承担；所有任务价值相同，目标是最大化被分配任务数。

输出包括匹配边的原始编号，以及由左侧人员和右侧任务组成的点覆盖。点覆盖必须接触每条资格边，不能把集合覆盖中的“覆盖所有目标”直接套到这里：这里覆盖的是图的边。

验证先检查匹配边都在输入中，左右端点没有重复，再检查点覆盖接触所有资格边。如果匹配大小等于点覆盖大小，就得到最优证书。理由是任何匹配的边两两不共享端点，而点覆盖必须为每条匹配边提供至少一个端点，所以任意匹配大小都不超过任意点覆盖大小。

当两者相等时，下界与上界夹住最大匹配值。这是确定性的证明，不依赖随机抽样或运行速度。27篇通过单位容量流与残量可达性构造这两个对象；本篇只复用接口，不另写一套增广路。

若最大匹配大小小于b，说明在这个固定资格图与一人一任务限制下，不能分配全部任务。它没有说明增加人员、拆分时段或改变任务集合后仍不可行。偏好、公平性、同人跨时段冲突也不在输入中，不能从最优证书推导出来。

最低成本覆盖：允许重复覆盖目标

输入为有限目标集U、候选集合S₀到Sₛ₋₁及对应正整数成本cᵢ。每个Sᵢ都是U的子集，可以为空；同一目标可被多个集合覆盖。要求选出的集合并集等于U，使所选成本之和最小。

空目标集的最优答案是空选择、成本0。若所有候选集合的并集仍缺少某个目标，就报告无法完全覆盖，不返回一个看似完整的近似解。这里只讨论正成本的小实例，底层30篇实现允许零成本，但不需要为综合项目扩大输入范围。

加权贪心每轮选择成本除以新覆盖目标数最小的集合，平局按输入编号。比例用有理数精确比较，避免浮点舍入改变平局。目标是最小化总成本，不是最少集合数，也不是固定预算下尽量多覆盖。

把近似保证变成可检查的不等式

设d是候选集合的最大大小，H_d=1+1/2+…+1/d。非空可覆盖实例必有d≥1。贪心选中集合时，把它的成本平均分摊给本轮新覆盖元素，记每个元素的分摊为αₑ。每个元素只收取一次，所以总分摊等于选中集合总成本C。

固定任何候选集合Sᵢ，考虑它的元素被覆盖的顺序。在尚有r个该集合元素未覆盖时，选择Sᵢ本身能提供成本至多cᵢ/r的新增覆盖比例。贪心选到的比例不会更高，因此这些元素的分摊总和至多cᵢH_|Sᵢ|，进一步至多cᵢH_d。同一轮覆盖多个元素时，各自分摊相同，按任意顺序排列仍满足这个上界。

令yₑ=αₑ/H_d，则对每个候选集合都有：

∑e∈Siye≤ci,ye≥0.\sum_{e\in S_i}y_e\le c_i,\qquad y_e\ge0.

这些就是覆盖线性规划的对偶可行条件。对任何可行整数覆盖，其成本至少为所有yₑ之和，因为它覆盖每个元素至少一次。于是得到：

C=Hd∑e∈Uye≤Hd OPT.C=H_d\sum_{e\in U}y_e\le H_d\,OPT.

检查程序可以独立验证y非负、每个集合约束、选择确实覆盖U，以及总成本与分摊关系。这证明一个H_d近似界，不证明C等于OPT；小实例的OPT仍交给独立子集穷举计算。空U单独处理，不计算H₀的除法。

两张证书不能拼成联合最优

设目标只有一个，便宜方案A成本1、较贵方案B成本2，都能覆盖它。唯一人员只具备执行B的资格。单独的覆盖贪心选择A完全正确，也满足近似保证；随后只对A做匹配会失败，但选择B就存在完整安排。

因此，“先覆盖，再对所选集合分配人员”在这里不能用来判断整个联合问题无解。匹配证书只约束已经固定的资格图，覆盖证书只比较没有人员限制的覆盖问题。若真正目标是最低成本且可安排的覆盖，需要把人员约束加入优化模型，重新分析算法。

另一个边界是把成本最低误写为集合数最少。一个集合覆盖两个目标、成本100，两个单元素集合各成本1；最少集合数答案与最低成本答案显然不同。输入输出契约比复用哪个算法名字更早决定正确性。

成本与可复跑检查

匹配复用27篇单位流实现，记N=a+b+2、M=m+a+b，初始化和增广的图操作界为O(N+(min(a,b)+1)M)。验证给定匹配与点覆盖只需扫描节点和资格边，O(N+m)操作。这里没有容量大小引入的伪多项式迭代，也不是任意最大流实现共有的更紧界。

集合覆盖复用逐轮扫描版本。记u=|U|、s为集合数，每轮至少覆盖一个新元素，至多u轮；每轮对所有集合求交，对非空可覆盖实例保守计O(su²)集合元素操作。若计入空目标集、无候选集合等输入的检查与复制，整个接口可用O(1+u+s+su²)作保守操作界。Python哈希集合成本按期望分析，有理数比较另计整数位长；这不是无条件最坏机器时间界。检查全部对偶约束只需遍历集合关联项并累加有理数。穷举参照遍历2ˢ个候选子集，限制在小s；它不是可扩展的生产求解器。

教学程序assignment_cover.py提供qualified_assignment、coverage_plan和只用于小实例的exact_cover。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_assignment_cover.py

本次实际退出0、status=passed：1885个穷举覆盖实例中1407个可覆盖、478个不可覆盖；另外检查100个固定种子随机实例、16个匹配证书、两个问题边界反例、空图与空目标集，以及8次非法参数拒绝。原始输出保存在writing-plans/advanced-algorithms/evidence/assignment-cover-results.json。

覆盖参照独立枚举所有候选子集，既比较成本界，也核对对偶价格；匹配检查合法性、点覆盖与大小相等。程序还复现“便宜方案无执行资格、较贵方案可安排”的反例。有限检查支持这些实现与实例，不替代上述一般证明；没有测量真实排班质量或生产性能。

练习

  1. 有两名人员、三个任务，所有资格边都连接到第一名人员。给出一个最大匹配和同大小点覆盖，解释证书为何足以排除分配三个任务。
  2. 为U={a,b,c}设计三个正成本候选集合，手算每轮新覆盖元素的α与y。检查所有对偶约束，再穷举最优成本；近似证书和最优证书各回答了什么问题？

参考资料