→ 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 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.129.28.142 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579705880.A.AE2.html ※ 编辑: Moderator (220.129.28.142 台湾), 01/22/2020 23:18:12