To which Knapsack-problem variation does this problem correspond?

Question

Let us imagine that I have to fill my knapsack with items under constraints:

• Each item has an associated weight wi and profit pi
• With a maximum total weight Wmax

Knowing that:

• There are categories of items and I have to choose exactly one item from each category
• Of course, the aim is to choose items to maximise the sum of the profits

Example : Wmax=400

Books	Books weights	Books profits	Food	Food weights	Food profits
The Bible	500	25	Cheese	80	120
The little prince	150	5	Banana	250	200

Here, the best solution is (The little prince, Banana)

I have a similar problem and I'd like to find out the best way to code it but I can't figure out what version/ variation of the probleme this is, is it a known variation ?

Answer 1

I’m not sure if there’s an existing variation that matches yours, but it’s easy to draw inference from the classical variant and solve this.

Classic variant has 2D dynamic programming (DP[N][W], where N and W are number of items and max weight).

In this variant, since we can only pick one of each category, you can use 3D DP like dp[i][w][j], which denotes the maximum value you can get from the first i items with weight w and j is a 0/1 int denoting whether an item from category number j has been selected or not.

I’ll leave the implementation, since the recursive relation is relatively simple and quite similar to the classic variant.