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