作者gash55025502 (白影弓)
看板Grad-ProbAsk
标题[理工] 交大108资演 题组15
时间Mon Dec 16 16:19:14 2019
https://i.imgur.com/yjPlqqI.jpg
大家好 想问这题的後面两小题
交大答案都是给A
想请问用什麽方法可以达到O(n)的时间呢？
因为我能想到的好像也都是要先排序好 这样就花nlogn了
感谢大大
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.139.15.158 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576484356.A.B64.html
1F：→ cossetannie: counting sort 12/16 16:23
2F：→ gash55025502: 楼上 他有给vi的值域吗 为什麽可以用counting sort 12/16 17:15
3F：推 mistel: 问一下这个knapsack是指部分背包吗？他也没有定义出他的 12/16 18:33
4F：→ mistel: 问题 12/16 18:33
5F：→ gash55025502: 我是把他当01背包来解 12/16 18:33
6F：推 mistel: 不知道属於[U]算不算给出值域 不过也知道U是大於2^32而已 12/16 18:40
7F：→ mistel: ... 12/16 18:40
8F：推 mistel: 不好意思我没跟上 那为什麽01背包还要排序？有什麽帮助吗 12/16 18:42
9F：→ mistel: ？ 12/16 18:42
10F：推 mistel: 喔等等我看懂了 脑袋打结 12/16 18:44
11F：推 pyramidinc: 第二小题如果说排序然後greedy解 O(n) 我还算能理解 12/16 18:48
12F：→ pyramidinc: 那为什麽第三小题也是O(n)呢？ 12/16 18:48
13F：推 mistel: +1同问，我发现我上个月写的时候写DBD orz 12/16 18:53
14F：推 pyramidinc: 我也写dbd 哈哈 这份超难orz 很多演算法的东西 偏偏我 12/16 19:00
15F：→ pyramidinc: 演算法又最弱 12/16 19:00
16F：推 mistel: 我觉得今年真的爆干难QQQ 我记得写完演算法後崩溃到蹲在 12/16 19:03
17F：→ mistel: 我学校操场怀疑人生 12/16 19:03
18F：→ mistel: 然後再往前写发现跟今年真是不一样的世界，难道出题教授 12/16 19:04
19F：→ mistel: 觉得出选择就可以难一点吗== 12/16 19:04
20F：→ pyramidinc: 别难过 这份我37分而已 应该可以安慰到你... 12/16 19:05
21F：→ gash55025502: 不知道有没有人可以提供立宇题库班的解答xd 12/16 22:24
22F：推 b10007034: 这题的下面两题都用DP，都可以O(n) 12/17 00:20
23F：→ gash55025502: b大可以稍微讲详细一点吗QQ想不出来怎麽用DP解到O(n 12/17 11:27
24F：→ gash55025502: ) DP不是都要O(nm)吗 12/17 11:27
25F：推 b10007034: 我想错了，拍谢 12/17 11:37
26F：→ b10007034: 後来才看懂题目，第二题可以counting sort的话 12/17 11:37
27F：→ b10007034: 第三题也可以，先把重量为2的value都除以2（O(n)）， 12/17 11:37
28F：→ b10007034: 然後counting sort 12/17 11:37
29F：→ b10007034: O(n) 12/17 11:37
30F：→ gash55025502: 但第三题sort完可以用greedy取吗？因为他的weight可 12/17 11:41
31F：→ gash55025502: 能1或2 不像第二题只有1 12/17 11:41
32F：推 b10007034: 是说题目这样设计，包包有过载的情况吗？ 12/17 11:46
33F：→ gash55025502: 过载是什麽意思？ 12/17 11:49
34F：推 jeremyyuan: 第三题我当初的想法是 用01取 所以是O(mn) 然後因为m= 12/17 13:04
35F：→ jeremyyuan: a*2^0+b*2^1 所以会是O(c*n)=O(n) 12/17 13:04
36F：推 FRAXIS: 第二题是 O(n lg n)，应该是不能 counting sort。 12/29 11:57
37F：推 FRAXIS: 第二题应该是 O(n) 我回文解释如何解第三题 12/29 12:15
38F：推 zaqxsw2230: 我觉得第二题就是考虑最sort而已，用midium of midian 01/30 20:52
39F：→ zaqxsw2230: (不知道有没有拼错) 01/30 20:53
40F：→ zaqxsw2230: 然後他给m=theta(n^2) 所以就把它全取...就O(n)? 我是 01/30 20:54
41F：→ zaqxsw2230: 这样想的 01/30 20:54