作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] 交大108资演 题组15
时间Sun Dec 29 12:14:52 2019
※ 引述《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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577592894.A.090.html
1F：推 mistel: 请问第二题如果没sorting不是可能会花上O(n^2)找价值最大 12/29 12:38
2F：→ mistel: 的吗：（ 12/29 12:38
3F：推 mistel: 因为我们不知道这回合的最大价值物品在哪里？ 12/29 12:42
4F：推 ccapricorntw: 不需要知道阿 只有n个物品 总重就n而已 但m是n^2 12/29 15:01
5F：→ ccapricorntw: 所以直接全选 12/29 15:01
6F：→ FRAXIS: m 也有可能比 n 小，不过只要用 selection algorithm 12/29 23:01
7F：→ FRAXIS: 就可以在 O(n) 时间解第二题 12/29 23:01
8F：推 ccapricorntw: 咦 m的n^2不是tight bound吗？ 不会比n小吧？ 12/29 23:19
9F：→ FRAXIS: 如果是这样解读的话，那 2 和 3 小题就全选就好了 12/30 07:16
10F：→ FRAXIS: 根本就不用设计任何演算法 12/30 07:16
11F：推 b10007034: 同意，完全不会过载就全选XD 12/30 17:03
12F：推 mistel: 懂了 感谢！！ 12/30 23:11