[理工] 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

继续阅读