To which Knapsack-problem variation does this problem correspond?

user_18513527 0
Viewed 187

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 ?

knapsack-problem dynamic-programming math optimization algorithm
1 Answers

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.

user_93507200
Related