作者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/cn.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