[理工] 109中央演算法 seafoodccu PTT批踢踢實業坊

作者: seafoodccu (c-看看你) 2021-01-09 15:37:51

想問一下
https://i.imgur.com/T8MPraq.jpg
不知道這三題該怎麼下筆QQ，跪求大神分享解法，謝謝！

作者: mathtsai (mathtsai) 2021-01-09 19:26:00

第一次看到會不知道怎麼下筆但是看C就知道是dphttps://reurl.cc/E2KGk0 提供dp參考這個問題叫做subset sum problem是NP-complete問題至於b 你需要找到一個NP-complete可以reduce成這個問題

作者: wwndbk (黑人問號) 2021-01-09 19:35:00

(b)(c) 小題在105中央有出過用類似01背包的演算法去寫可以得到pseudo-polynomial

作者: seafoodccu (c-看看你) 2021-01-09 20:26:00

想再問一下(b)小題，該用什麼problem來reduce會比較好？

作者: joywilliamjo (joywilliamjoy) 2021-01-09 20:41:00

用subset problem,subset size = k?

作者: aa871220 (TMVP_Yueko) 2021-01-10 15:58:00

也可以用3cnf sat做reduce

繼續閱讀