Re: [理工] 交大108資演 題組15

[FRAXIS (喔喔)]

※ 引述《gash55025502 (白影弓)》之銘言：
: https://i.imgur.com/yjPlqqI.jpg
: 大家好 想問這題的後面兩小題
: 交大答案都是給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
推 mistel: 請問第二題如果沒sorting不是可能會花上O(n^2)找價值最大
→ mistel: 的嗎：（
推 mistel: 因為我們不知道這回合的最大價值物品在哪裡？
推 ccapricorntw: 不需要知道阿 只有n個物品 總重就n而已 但m是n^2
→ ccapricorntw: 所以直接全選
→ FRAXIS: m 也有可能比 n 小，不過只要用 selection algorithm
→ FRAXIS: 就可以在 O(n) 時間解第二題
推 ccapricorntw: 咦 m的n^2不是tight bound嗎？ 不會比n小吧？
→ FRAXIS: 如果是這樣解讀的話，那 2 和 3 小題就全選就好了
→ FRAXIS: 根本就不用設計任何演算法
推 b10007034: 同意，完全不會過載就全選XD
推 mistel: 懂了 感謝！！