[理工] 109中央 演算法

看板Grad-ProbAsk作者 (c-看看你)時間3年前 (2021/01/09 15:37), 3年前編輯推噓4(4推 0噓 6→)
留言10則, 5人參與, 3年前最新討論串1/1
想問一下 https://i.imgur.com/T8MPraq.jpg
不知道這三題該怎麼下筆QQ，跪求大神分享解法，謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.104.18.31 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1610177873.A.8E9.html ※ 編輯: seafoodccu (112.104.18.31 臺灣), 01/09/2021 15:38:17
推
01/09 19:26, 3年前 , 1F
第一次看到會不知道怎麼下筆 但是看C就知道是dp
01/09 19:26, 1F
→
01/09 19:28, 3年前 , 2F
01/09 19:28, 2F
→
01/09 19:29, 3年前 , 3F
這個問題叫做subset sum problem是NP-complete問題
01/09 19:29, 3F
→
01/09 19:30, 3年前 , 4F
至於b 你需要找到一個NP-complete可以reduce成這個問題
01/09 19:30, 4F
推
01/09 19:35, 3年前 , 5F
(b)(c) 小題在105中央有出過
01/09 19:35, 5F
→
01/09 19:36, 3年前 , 6F
用類似01背包的演算法去寫可以得到pseudo-polynomial
01/09 19:36, 6F
→
01/09 20:26, 3年前 , 7F
想再問一下(b)小題，該用什麼problem來reduce會比較好
01/09 20:26, 7F
→
01/09 20:26, 3年前 , 8F
？
01/09 20:26, 8F
推
01/09 20:41, 3年前 , 9F
用subset problem,subset size = k?
01/09 20:41, 9F
推
01/10 15:58, 3年前 , 10F
也可以用3cnf sat做reduce
01/10 15:58, 10F
‣ 更多 seafoodccu 的文章
文章代碼(AID): #1V-LrHZf (Grad-ProbAsk)