[理工] 108交大資演15

看板Grad-ProbAsk作者 (Kobe Mary)時間5年前 (2020/01/18 23:01), 編輯推噓1(1推 0噓 4→)
留言5則, 3人參與, 5年前最新討論串1/2 (看更多)
答案是daa 請問01knapsack 應該是pseudo polynomial，為什麼 33 還可以寫成這樣？ 34 35 我不知道為什麼w都設1的時候時間變那樣。34 我的想法是對各物品value排序，從 大開始取，但也不知道對不對 https://i.imgur.com/bvN7oJi.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579359679.A.419.html
→
01/18 23:34, 5年前 , 1F
34 每個重量都只有1 全部拿
01/18 23:34, 1F
→
01/18 23:35, 5年前 , 2F
35也是 最主要是它output 要印出所有東西 所以是O(n)
01/18 23:35, 2F
→
01/19 09:31, 5年前 , 3F
l大 是因為m=n^2 所以包包足夠大 才可以直接全拿？
01/19 09:31, 3F
推
01/19 13:39, 5年前 , 4F
33 是原版複雜度就是nW, 其他兩題就是因為包包夠大可以
01/19 13:39, 4F
→
01/19 13:39, 5年前 , 5F
全拿
01/19 13:39, 5F
‣ 更多 dsa66253 的文章
文章代碼(AID): #1U8ns_GP (Grad-ProbAsk)
‣ 更多 dsa66253 的文章
文章代碼(AID): #1U8ns_GP (Grad-ProbAsk)