知识卡片

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

精确子集和逐项扩展列表

理解等级:中级

处理前i个数时,维护不超过目标t的所有可达子集和列表L_i;下一轮合并旧列表与每个旧值加上x_i的列表,去重并删除超出t的值。

状态可能增长到2^i,因此精确法一般为指数时间。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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