知识卡片

普通读书笔记卡 · 3719.b.1.a.1

子集和近似每轮小幅修剪

理解等级:高级

输入S={x₁,…,xₙ}是一组正整数,t是允许的最大目标和,0<ε是误差参数。列表Lᵢ保存处理前i个数后仍保留的真实可达子集和,初始L₀=〈0〉。第i轮:

  1. 合并Lᵢ₋₁与Lᵢ₋₁+xᵢ;后一列表表示在原子集上再选xᵢ。
  2. 令δ=ε/(2n),按递增顺序修剪。保留第一个值;之后仅当当前值y>last×(1+δ)时才保留,并更新last。被删的y由留下的last代表,满足last≤y≤last×(1+δ)。
  3. 删除大于t的值,最后返回Lₙ中的最大值。

合并不会制造虚构答案,修剪和删除也只去掉值,所以输出仍是某个真实子集的和。把ε分摊到n轮,是为了让每轮至多1+δ的代表误差在连乘后仍受1+ε控制。

原书示例取n=4、ε=0.40,因此δ=0.40/(2×4)=0.40⁄8=0.05;书中“0.40/80”是分母排印错误,数值0.05及后续列表使用正确。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[45000,50000))。 - 结论依据:第35章35.5节给出TRIM的扫描保留规则和APPROX-SUBSET-SUM三步循环;示例参数按δ=ε/(2n)复算,确认“0.40/80”应为“0.40/8”。 - 原始内容:Given the procedure T RIM , the procedure A PPROX -S UBSET -S UM on the following page implements the approximation scheme. This procedure takes as input a set S = { x 1 , x 2 , … , x n } of n integers (in arbitrary order), the size n = | S |, the target integer t , and an approximation parameter ϵ , where It returns a value z * whose value is