※ 引述《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)。