np-hard证明实例 规约

5. Subset sum problem 2A。

        2A−k所在的子集的其它元素就是一个满足子集和问题的子集。

7. Partition problem 构造背包问题中一个物品item u 且大小s(u)=价值w(u)=t, 然后对背包容量 B,最小价值K添加如下条件，即等于和的一半

         那么有

         体积符合要求、总价值符合要求，所以是背包问题的解。

Q的输出转换为P的输出：

         因为此时的U'正好等于U的一半，所以划分问题也有解。

P问题、NP问题、NPC问题的概念及实例证明_金良山庄-CSDN博客_np问题举例