→ MASAGA: 題目說要output O(n)是花在output上 01/22 23:52
→ Moderator: 感謝 一語點醒夢中人 01/22 23:57
→ 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1579705880.A.AE2.html
※ 編輯: Moderator (220.129.28.142 臺灣), 01/22/2020 23:18:12