[理工] 交大108资演题组15 gash55025502 PTT批踢踢实业坊

楼主: gash55025502 (白影弓) 2019-12-16 16:19:14

https://i.imgur.com/yjPlqqI.jpg
大家好想问这题的后面两小题
交大答案都是给A
想请问用什么方法可以达到O(n)的时间呢？
因为我能想到的好像也都是要先排序好这样就花nlogn了
感谢大大

作者: cossetannie (paa) 2019-12-16 16:23:00

counting sort

楼主: gash55025502 (白影弓) 2019-12-16 17:15:00

楼上他有给vi的值域吗为什么可以用counting sort

作者: mistel (Mistel) 2019-12-16 18:33:00

问一下这个knapsack是指部分背包吗？他也没有定义出他的问题

楼主: gash55025502 (白影弓) 2019-12-16 18:33:00

我是把他当01背包来解

作者: mistel (Mistel) 2019-12-16 18:40:00

不知道属于[U]算不算给出值域不过也知道U是大于2^32而已...不好意思我没跟上那为什么01背包还要排序？有什么帮助吗？喔等等我看懂了脑袋打结

作者: pyramidinc (PyramidInc) 2019-12-16 18:48:00

第二小题如果说排序然后greedy解 O(n) 我还算能理解那为什么第三小题也是O(n)呢？

作者: mistel (Mistel) 2019-12-16 18:53:00

+1同问，我发现我上个月写的时候写DBD orz

作者: pyramidinc (PyramidInc) 2019-12-16 19:00:00

我也写dbd 哈哈这份超难orz 很多算法的东西偏偏我算法又最弱

作者: mistel (Mistel) 2019-12-16 19:03:00

我觉得今年真的爆干难QQQ 我记得写完算法后崩溃到蹲在我学校操场怀疑人生然后再往前写发现跟今年真是不一样的世界，难道出题教授觉得出选择就可以难一点吗==

作者: pyramidinc (PyramidInc) 2019-12-16 19:05:00

别难过这份我37分而已应该可以安慰到你...

楼主: gash55025502 (白影弓) 2019-12-16 22:24:00

不知道有没有人可以提供立宇题库班的解答xd

作者: b10007034 (Warren) 2019-12-17 00:20:00

这题的下面两题都用DP，都可以O(n)

楼主: gash55025502 (白影弓) 2019-12-17 11:27:00

b大可以稍微讲详细一点吗QQ想不出来怎么用DP解到O(n) DP不是都要O(nm)吗

作者: b10007034 (Warren) 2019-12-17 11:37:00

我想错了，拍谢后来才看懂题目，第二题可以counting sort的话第三题也可以，先把重量为2的value都除以2（O(n)），然后counting sortO(n)

楼主: gash55025502 (白影弓) 2019-12-17 11:41:00

但第三题sort完可以用greedy取吗？因为他的weight可能1或2 不像第二题只有1

作者: b10007034 (Warren) 2019-12-17 11:46:00

是说题目这样设计，包包有过载的情况吗？

楼主: gash55025502 (白影弓) 2019-12-17 11:49:00

过载是什么意思？

作者: jeremyyuan (阿元) 2019-12-17 13:04:00

第三题我当初的想法是用01取所以是O(mn) 然后因为m=a*2^0+b*2^1 所以会是O(c*n)=O(n)

继续阅读