askhelper's blog

Knapsack problem modification
By askhelper, 6 years ago, In English

How to solve knapsack problem efficiently if we are given the count of items (i.e. we can buy i'th item cnti times)? I'm looking for something like O(n·C) or O(n·C·log(cnt)) (you got the idea) where C is the capacity of the knapsack. Any ideas are appreciated.

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

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

Is there a link to the problem or is it your own problem?

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

    I just came up with this few hours ago.

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

      Ok, my solution would be: Look at each cnti's binary representation and split it into O(logcnti) items accordingly. For example, if cnti = 259, we split it into 3 items: one with cost ci * 256 and value vi * 256, one with cost ci * 2 and value vi * 2 and one with cost ci and value vi. Though note that this doesn't, for example, account for buying 128 of that item. So we go from the highest bit to the lowest, and if we have at least 1 item that represents the current bit and 0 items that represent the bit that is 2 times less significant, we split one of the items representing that bit into 2 items with 2 times smaller value and cost. Now each of the O(n * log(cnt)) new elements can be chosen 0 or 1 times, which can obviously be solved by knapsack in O(n * C * log(n)).

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

That will do the trick:

We will create some "offers" and do standard knapsack on them. For each item, add the offer (WEIGHT, VALUE) for each WEIGHT = wi * 2j such that WEIGHT does not exceed C (of course, VALUE = vali * 2j in this case). Also, add (wi * (cnti - X), vali * (cnti - X)) where X is largest 2a - 1 that is smaller than cnti. The rest is easy knapsack.

P.S. This is almost the same solution as dorijanlendvaj's.

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

This is the bounded knapsack problem. Petr has outlined the two common solutions here: https://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html

→ Reply