prabhat7298's blog

Unlimited amount, big knapsack, small items
By prabhat7298, history, 5 years ago, In English

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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Probably not, for this particular set of constraints

      → Reply