[理工] 109中央 演算法

[seafoodccu (c-看看你)]

想問一下

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
推 mathtsai: 第一次看到會不知道怎麼下筆 但是看C就知道是dp
→ mathtsai: https://reurl.cc/E2KGk0 提供dp參考
→ mathtsai: 這個問題叫做subset sum problem是NP-complete問題
→ mathtsai: 至於b 你需要找到一個NP-complete可以reduce成這個問題
推 wwndbk: (b)(c) 小題在105中央有出過
→ wwndbk: 用類似01背包的演算法去寫可以得到pseudo-polynomial
→ seafoodccu: 想再問一下(b)小題，該用什麼problem來reduce會比較好
→ seafoodccu: ？
推 joywilliamjo: 用subset problem,subset size = k?
推 aa871220: 也可以用3cnf sat做reduce