Set Cover 的贪心近似

每轮选择只为尚未覆盖的元素创造价值，因此分母必须随覆盖状态缩小。把集合成本平均收给本轮新覆盖元素后，任意最优集合中第 $j$ 个较晚被覆盖的元素，面对的剩余候选只会更少；这些收费形成调和级数，而不是每轮都付同一个最坏比率。

真实选择图像 ​

布置监测站覆盖一组区域时，一个站虽覆盖面大但成本也高；加权规则比较“每新增覆盖一个尚未监测区域的成本”，已覆盖区域不再贡献分母。无权规则若直接用于成本差异大的站点，会偏离证明。

边界与相邻问题 ​

$H_{|U|}\approx \ln |U|+1$ 不是常数，且在标准复杂度假设下对数量级基本紧。最大覆盖问题给定只能选 $k$ 个集合、目标最大化覆盖量，具有不同的 $1-1/e$ 分析。参数 $|U|$ 是宇宙元素数；若改用最大集合大小可得更细 $H_d$，必须明确 $d$。

算法每步选择单位成本覆盖新元素最多的集合，是贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。；调和数近似保证来自把每个新覆盖元素按当步单位代价收费，并与最优解中某个集合尚未覆盖的元素数比较。

实现与 tie-breaking ​

直接每轮重算所有集合新增覆盖成本可能为 $O(|U||\mathcal{S}|)$ 甚至更高。无权版可维护按当前 uncovered count 的桶或懒优先队列；选出候选后重新计算其真实新增量，过期键就更新再弹。加权比率是有理数，比较可交叉相乘避免浮点误判。

平局任取都保留近似证明，因为只用“单位成本不大于任何候选”。但输出若要求可重复，仍应以集合 ID 固定 tie-break。预处理还要确认每个元素至少属于一个集合，否则实例不可覆盖。

加权实例的选择轨迹 ​

设未覆盖元素为 6 个，集合 $A$ 成本 3 可新增覆盖 3 个，$B$ 成本 2 可新增覆盖 1 个，$C$ 成本 4 可新增覆盖 5 个。当前单位新增成本分别为 1、2、0.8，所以先选 $C$；重算后 $A$ 也许只剩一个新元素，比例会从 1 变为 3，不能沿用初始排序。

实现可用懒堆保存上次计算的比例：弹出候选后按当前未覆盖集重算，只有仍不劣于堆顶才真正选择，否则以新键放回。这个技巧减少实际重算，却不改变最坏近似证明；tie-breaking 影响具体解，不影响 $H_{|U|}$ 上界。

若某元素不属于任何集合，实例本身不可行，算法应在 $R$ 非空而所有新增覆盖为零时报告失败。最大覆盖问题有选择个数预算、目标是尽量多覆盖，与“必须覆盖全部元素”的 Set Cover 方向不同。