作者seafoodccu (c-看看你)
看板Grad-ProbAsk
標題[理工] 109中央 演算法
時間Sat Jan 9 15:37:51 2021
想問一下
https://i.imgur.com/T8MPraq.jpg
不知道這三題該怎麼下筆QQ，跪求大神分享解法，謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.104.18.31 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1610177873.A.8E9.html
※ 編輯: seafoodccu (112.104.18.31 臺灣), 01/09/2021 15:38:17
1F：推 mathtsai: 第一次看到會不知道怎麼下筆 但是看C就知道是dp 01/09 19:26
3F：→ mathtsai: 這個問題叫做subset sum problem是NP-complete問題 01/09 19:29
4F：→ mathtsai: 至於b 你需要找到一個NP-complete可以reduce成這個問題 01/09 19:30
5F：推 wwndbk: (b)(c) 小題在105中央有出過 01/09 19:35
6F：→ wwndbk: 用類似01背包的演算法去寫可以得到pseudo-polynomial 01/09 19:36
7F：→ seafoodccu: 想再問一下(b)小題，該用什麼problem來reduce會比較好 01/09 20:26
8F：→ seafoodccu: ？ 01/09 20:26
9F：推 joywilliamjo: 用subset problem,subset size = k? 01/09 20:41
10F：推 aa871220: 也可以用3cnf sat做reduce 01/10 15:58