Re: [理工] 交大108資演 題組15
: 大家好 想問這題的後面兩小題
: 交大答案都是給A
: 想請問用什麼方法可以達到O(n)的時間呢？
: 因為我能想到的好像也都是要先排序好 這樣就花nlogn了
: 感謝大大
第一小題，使用標準的 DP 解法，應該是要 O(nm) = O(n^3) 時間。
第二小題，因為每個物品的重量都一樣，所以只要價值最大的 m 個物品就好了，
所以只要 O(n) 時間（當 m 比 n 大時，就直接選全部）。
第三小題，因為物品的重量頂多是 2 ，所以全部物體的重量也頂多是 2n 而已。
使用標準的 DP 解法需要 O(n * 2n) = O(n^2)。
不過你可以先把重量為 1 的物品按照 value 遞減排序，
然後把重量為 2 的物品按照 value 遞減排序。
先從重量為 1 的物品中挑 m 個 value 最高的出來。
然後試著移除兩個重量為 1 的物品，換重量為 2 的最高 value 物品，看
能不能得到更佳解。一直持續這過程直到不能再找到更佳解為止。
時間是花在排序上，所以需要 O(n lg n)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577592894.A.090.html
推
12/29 12:38,
6年前
, 1F
12/29 12:38, 1F
→
12/29 12:38,
6年前
, 2F
12/29 12:38, 2F
推
12/29 12:42,
6年前
, 3F
12/29 12:42, 3F
推
12/29 15:01,
6年前
, 4F
12/29 15:01, 4F
→
12/29 15:01,
6年前
, 5F
12/29 15:01, 5F
→
12/29 23:01,
6年前
, 6F
12/29 23:01, 6F
→
12/29 23:01,
6年前
, 7F
12/29 23:01, 7F
推
12/29 23:19,
6年前
, 8F
12/29 23:19, 8F
→
12/30 07:16,
6年前
, 9F
12/30 07:16, 9F
→
12/30 07:16,
6年前
, 10F
12/30 07:16, 10F
推
12/30 17:03,
6年前
, 11F
12/30 17:03, 11F
推
12/30 23:11,
6年前
, 12F
12/30 23:11, 12F
討論串 (同標題文章)
