In most of the knapsack variants we've a linear dependency on the knapsack size M but in case where we've many small items leading to a very large knapsack capacity we need an alternate way of solving it. I read about it here that we can solve it by using shortest path algorithm but I wasn't able to grab the whole concept. Can anyone explain it in simpler words and can comment a little on the implementation part. Here you can find a related problem.
Interesting post!
Can anyone explain why the complexity stated in the first link is $$$O(w^\frac{3}{2} + nw)$$$ and not $$$O(w^2 + nw)$$$? Also, why does the solution of complexity $$$O(n w \log{w})$$$ pass the tests of the problem in no time? Should that not exceed TL?
Solution
bicsi Thanks for the code. understood it! Btw is it possible to answer queries asking maximum value we can obtain for a weight if along with original weights corresponding values are also given?
Probably not, for this particular set of constraints