知识卡片
子集和近似每轮小幅修剪
输入S={x₁,…,xₙ}是一组正整数,t是允许的最大目标和,0<ε是误差参数。列表Lᵢ保存处理前i个数后仍保留的真实可达子集和,初始L₀=〈0〉。第i轮:
- 合并Lᵢ₋₁与Lᵢ₋₁+xᵢ;后一列表表示在原子集上再选xᵢ。
- 令δ=ε/(2n),按递增顺序修剪。保留第一个值;之后仅当当前值y>last×(1+δ)时才保留,并更新last。被删的y由留下的last代表,满足last≤y≤last×(1+δ)。
- 删除大于t的值,最后返回Lₙ中的最大值。
合并不会制造虚构答案,修剪和删除也只去掉值,所以输出仍是某个真实子集的和。把ε分摊到n轮,是为了让每轮至多1+δ的代表误差在连乘后仍受1+ε控制。
原书示例取n=4、ε=0.40,因此δ=0.40/(2×4)=0.40⁄8=0.05;书中“0.40/80”是分母排印错误,数值0.05及后续列表使用正确。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
Given the procedure TRIM, the procedure APPROX-SUBSET-SUM on the following page implements the approximation scheme. This procedure takes as input a set S = {x1, x2,
参考来源
- 位置:《算法导论(第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