作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题[理工] 109 清大 计算机科学 演算法 第九题
时间Mon Nov 29 23:22:24 2021
https://i.imgur.com/9q4cbPz.jpg
这题有办法用题目给的2 partition去证出 3 partition也是NPC吗？
我知道两个reduce到subset sum
但用subset sum去证的话会不会不够严谨？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.136.161.51 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1638199346.A.78B.html
1F：推 foogty: 我的想法是这样，构建一个新集合S'为S集合再添加一个新的11/30 07:24
2F：→ foogty: 数字k,当S'存在3 partition 则 S存在 2 partition, S中存11/30 07:24
3F：→ foogty: 在2 partition 也可以推到S'中存在3 partition ,不晓得这11/30 07:24
4F：→ foogty: 样是不是对的11/30 07:24
5F：推 VF84: 楼上的想法很接近了，我帮他补充细节11/30 07:39
6F：→ VF84: 给定一个 multiset S，其元素总和为 2T，则在 S 中添加11/30 07:40
7F：→ VF84: T，就可以用 3-partition 去判断是否存在 2-partition11/30 07:40
9F：推 foogty: 感谢补充11/30 07:48
10F：→ joywilliamjo: 感谢，懂了11/30 09:53
11F：→ mathtsai: CLRS NPC reduce那章节应该有教吧11/30 18:42
有教怎麽全部reduce到subset sum,没有单纯的3partition到2partition
※ 编辑: joywilliamjo (101.136.64.176 台湾), 12/01/2021 15:51:38