作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
标题[理工] 108交大资演15
时间Sat Jan 18 23:01:17 2020
答案是daa
请问01knapsack 应该是pseudo polynomial，为什麽 33 还可以写成这样？
34 35 我不知道为什麽w都设1的时候时间变那样。34 我的想法是对各物品value排序，从
大开始取，但也不知道对不对
https://i.imgur.com/bvN7oJi.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 150.117.242.146 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579359679.A.419.html
1F：→ lau860908: 34 每个重量都只有1 全部拿 01/18 23:34
2F：→ lau860908: 35也是 最主要是它output 要印出所有东西 所以是O(n) 01/18 23:35
3F：→ dsa66253: l大 是因为m=n^2 所以包包足够大 才可以直接全拿？ 01/19 09:31
4F：推 a9778875: 33 是原版复杂度就是nW, 其他两题就是因为包包够大可以 01/19 13:39
5F：→ a9778875: 全拿 01/19 13:39