[理工] 109 清大 計算機科學 演算法 第九題

看板Grad-ProbAsk作者 (joywilliamjoy)時間4年前 (2021/11/29 23:22), 4年前編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 4年前最新討論串1/1
https://i.imgur.com/9q4cbPz.jpg
這題有辦法用題目給的2 partition去證出 3 partition也是NPC嗎？ 我知道兩個reduce到subset sum 但用subset sum去證的話會不會不夠嚴謹？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.136.161.51 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1638199346.A.78B.html
推
11/30 07:24, 4年前 , 1F
我的想法是這樣，構建一個新集合S'為S集合再添加一個新的
11/30 07:24, 1F
→
11/30 07:24, 4年前 , 2F
數字k,當S'存在3 partition 則 S存在 2 partition, S中存
11/30 07:24, 2F
→
11/30 07:24, 4年前 , 3F
在2 partition 也可以推到S'中存在3 partition ,不曉得這
11/30 07:24, 3F
→
11/30 07:24, 4年前 , 4F
樣是不是對的
11/30 07:24, 4F
推
11/30 07:39, 4年前 , 5F
樓上的想法很接近了，我幫他補充細節
11/30 07:39, 5F
→
11/30 07:40, 4年前 , 6F
給定一個 multiset S，其元素總和為 2T，則在 S 中添加
11/30 07:40, 6F
→
11/30 07:40, 4年前 , 7F
T，就可以用 3-partition 去判斷是否存在 2-partition
11/30 07:40, 7F
推
11/30 07:45, 4年前 , 8F
11/30 07:45, 8F
推
11/30 07:48, 4年前 , 9F
感謝補充
11/30 07:48, 9F
→
11/30 09:53, 4年前 , 10F
感謝，懂了
11/30 09:53, 10F
→
11/30 18:42, 4年前 , 11F
CLRS NPC reduce那章節應該有教吧
11/30 18:42, 11F
有教怎麼全部reduce到subset sum,沒有單純的3partition到2partition ※ 編輯: joywilliamjo (101.136.64.176 臺灣), 12/01/2021 15:51:38
‣ 更多 joywilliamjo 的文章
文章代碼(AID): #1XfF0oUB (Grad-ProbAsk)