What type of knapsack problem is this?

Question

I need to choose the highest value combination of items given a specific set of constraints. These constraints are:

1. Exactly 6 items from group A and 2 items from group B must be selected.
2. Items in group A and group B count towards the same maximum weight.
3. No item can be selected more than once.
4. No more than 2 items of the same 'color' can be selected (there is always exactly 2 of each color in group A and 1 of each color in group B).

Example data set:

Group A
Item - Weight - Value - Color
A01 - 32 - 59 - Teal
A02 - 31 - 65 - Teal
A03 - 29 - 57 - Red
A04 - 27 - 16 - Red
A05 - 25 - 07 - Orange
A06 - 25 - 20 - Purple
A07 - 24 - 06 - Orange
A08 - 23 - 39 - White
A09 - 22 - 20 - White
A10 - 21 - 23 - Purple
A11 - 21 - 31 - Blue
A12 - 20 - 16 - Green
A13 - 20 - 17 - Blue
A14 - 19 - 45 - Green
A15 - 18 - 22 - Black
A16 - 18 - 14 - Yellow
A17 - 17 - 08 - Yellow
A18 - 17 - 22 - Gray
A19 - 16 - 13 - Black
A20 - 16 - 26 - Gray

Group B
Item - Weight - Value - Color
B01 - 36 - 85 - Teal
B02 - 33 - 39 - Red
B03 - 31 - 48 - Purple
B04 - 30 - 28 - Orange
B05 - 29 - 71 - White
B06 - 24 - 65 - Blue
B07 - 23 - 64 - Green
B08 - 22 - 61 - Yellow
B09 - 21 - 36 - Black
B10 - 20 - 27 - Gray

Max weight = 200

---

I'm not necessarily looking for a solution to this problem. I have found all sorts of ways to solve many variations of problems that seem very similar to this, but none seem quite right. If I just knew what to look for, I'm sure I'd be able to find an example and figure out the rest from there.

The closest I've been able to get is an 0/1 multi-knapsack (or maybe multi-dimensional knapsack?) problem. Does anyone have a better description of this problem? Thanks in advance!

Edit: Oh, bonus question, if anyone has any recommendations for languages which are particularly well suited to this type of problem (I was thinking python for itertools), I'd greatly appreciate it.

Answer 1

Multi-dimensional knapsack seem appropriate. The additional dimensions are 1 if item is in group A, else 0, 1 if item is in group B, else 0, 1 if item is green, else 0, ... The maximum weights of additional dimensions are 6, 2 and then 2 for each color.

The condition that there must be exactly 6 items from group A could be forced by an additional dimension -1 if item is in group A, else 0 and maximum weight of -6. However, this is awkward.