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

counting sort

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

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

我是把他当01背包来解

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

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

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

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

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

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

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

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

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

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

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

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

过载是什么意思？

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