[理工] 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那章節應該有教吧

繼續閱讀