知识卡片
精确子集和逐项扩展列表
处理前i个数时,维护不超过目标t的所有可达子集和列表L_i;下一轮合并旧列表与每个旧值加上x_i的列表,去重并删除超出t的值。
状态可能增长到2^i,因此精确法一般为指数时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
, xn}, the size n = |S|, and a target value t. This procedure iteratively computes Li, the list of sums of all subsets of {x1,
参考来源
- 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[40000,45000))。
- 结论依据:第35章加权顶点覆盖、子集和近似方案或章末问题定义与注记;习题未证明的近似比不作已证结论。
- 原始内容:The procedure E XACT -S UBSET -S UM takes an input set S = { x 1 , x 2 , … , x n }, the size n = | S |, and a target value t . This procedure iteratively computes L i , the list of sums of all subsets of { x 1 , … , x i } that do not exceed t , and then it returns the maximum value in L n . If L is a list of positive integers and x is another