Knapsack with limit on total items used

2
votes

So, I have a knapsack where a number of items that can be placed into the knapsack has a limit, while the amount of weight of the items also has a limit.

So given item limit 5, and weight 100: We would find the 5 items (can repeat 5x same item) that best fit weight 100.

I have solved both unbounded and bounded(each item has a limit, but the total amount of items used has no limit) in dynamic programming. But I'm a bit confused with how to do this new approach. Would this be a multidimensional knapsack problem, like volume and weight? But instead, we want item's used and weight? Or is it a 0-1 knapsack with alterations?

If anyone able to break this down into smaller logical steps or point me in the direction of some solid code to read (my google-fu is struggling to find solutions) that would be greatly appreciated.

Thank you for your time!

2
pythonalgorithmknapsack-problem

2 Answers

1
votes

This is the multiply constrained knapsack problem. Your new constraint is that the sum of the number of items is less than some number unrelated to their weight.

There's some good approaches in here: http://www2.math.uni-wuppertal.de/~klamroth/publications/klwidp00.pdf

You should also try adapting the recurrence relation of the regular knapsack problems with your new constraint and see where you get.

1
votes

This can be formulated as a multiply constrained knapsack problem (also known as multidimensional knapsack problem) as follows.

The objective function and the first dimension remain the same as in your current formulation (i.e. the sum of weights).

The second dimension can then be used to constrain the number of selected items. Using Wikipedia notation:

  • w2,i = 1 for all i;
  • W2 = the limit on the number of items you're allowed to select (in your example, 5).

Here are some references: