知识卡片

普通读书笔记卡 · 3714.b.8.a

特殊情形可传递困难性

理解等级:中级

若NP难问题X是问题Y的特殊情形,Y的通用算法必然能处理X,因此Y也NP难。

例如将0-1背包的价值设为重量,并把重量上限与价值下限都设为总重量的一半,可嵌入集合划分判定问题。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      Look for special cases Several NP-complete problems are just special cases of other NP-complete problems. For example, consider the decision version of the 0-1 knapsack problem: given a set of n items, each with a weight and a value, does there exist a subset of items whose total weight is at most a given weight W and whose total value is at least

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[115000,120000))。 - 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。 - 原始内容:Look for special cases Several NP-complete problems are just special cases of other NP-complete problems. For example, consider the decision version of the 0-1 knapsack problem: given a set of n items, each with a weight and a value, does there exist a subset of items whose total weight is at most a given weight W and whose total value is at least