[理工] 109 清大计算机科学算法第九题 joywilliamjo PTT批踢踢实业坊

楼主: joywilliamjo (joywilliamjoy) 2021-11-29 23:22:24

https://i.imgur.com/9q4cbPz.jpg
这题有办法用题目给的2 partition去证出 3 partition也是NPC吗？
我知道两个reduce到subset sum
但用subset sum去证的话会不会不够严谨？

作者: foogty (夫葛踢) 2021-11-30 07:24:00

我的想法是这样，构建一个新集合S'为S集合再添加一个新的数字k,当S'存在3 partition 则 S存在 2 partition, S中存在2 partition 也可以推到S'中存在3 partition ,不晓得这样是不是对的

作者: VF84 (Jolly Roger) 2021-11-30 07:39:00

楼上的想法很接近了，我帮他补充细节给定一个 multiset S，其元素总和为 2T，则在 S 中添加T，就可以用 3-partition 去判断是否存在 2-partitionhttps://imgur.com/a/d2lrwtG.jpg

作者: foogty (夫葛踢) 2021-11-30 07:48:00

感谢补充

楼主: joywilliamjo (joywilliamjoy) 2021-11-30 09:53:00

感谢，懂了

作者: mathtsai (mathtsai) 2021-11-30 18:42:00

CLRS NPC reduce那章节应该有教吧

继续阅读