nagato_uzumaki's blog

bounded knapsack
By nagato_uzumaki, history, 4 years ago, In English

I was struggling to figure out states and transitions for bounded knapsack problem which is the most general case of knapsack problem, so please if someone can share some insights and code for this, it will be very helpful for us.

For those who may not be familiar with this term bounded knapsack:-

The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count si associated with it and we can select an item si times(at max) (1 ≤ i ≤ N).

Ok, finally I got this nice article written by Petr !

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can read this tutorial (which is also easy to search on google)

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

    yes, i have gone through it and i was wondering whether it is possible to calculate it in O(W) space complexity like 0/1 knapsack or not?, btw thanks for pointing out this good article here.

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

      whether it is possible to calculate it in O(W) like 0/1 knapsack or not?

      How can you solve $$$knapsack_{ 0/1}$$$ in $$$O(W)$$$ ?

      The effecient algorithm for unbounded knapsack I know is from this comment whose complexity is $$$O(N\ log\ N \times W)$$$. And from this blog

      → Reply