→ lau860908: 34 每个重量都只有1 全部拿 01/18 23:34
→ lau860908: 35也是 最主要是它output 要印出所有东西 所以是O(n) 01/18 23:35
→ dsa66253: l大 是因为m=n^2 所以包包足够大 才可以直接全拿？ 01/19 09:31
推 a9778875: 33 是原版复杂度就是nW, 其他两题就是因为包包够大可以 01/19 13:39
→ a9778875: 全拿 01/19 13:39
想借问同一题，可以理解全拿因为可负重量是theta(n^2)
而物品总重只有n (34题而言)
但是如果全拿不就可以O(1)根本不用O(n)的时间算?
还是因为还是要一个个去判断wi是否为1才能决定是否全拿呢?
谢谢~~
※ 引述《dsa66253 (Kobe Mary)》之铭言：
: 答案是daa
: 请问01knapsack 应该是pseudo polynomial，为什么 33 还可以写成这样？
: 34 35 我不知道为什么w都设1的时候时间变那样。34 我的想法是对各物品value排序，从
: 大开始取，但也不知道对不对
: https://i.imgur.com/bvN7oJi.jpg