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 ?
CodePudding user response：
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.