# Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution:

I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of classes, except for the last class in which I must select exactly three distinct items.

Each item has both a weight and a profit as an attribute.The goal is to maximize profit while not exceeding the maximum weight of the knapsack. There are a number of papers which suggest algorithms if exactly one item is chosen from each class (MCKP), but I have not found any which speak about a class which requires more than one to be selected.

The immediate solution that comes to mind is to treat the special class as the others by transforming it into a single selection of a combination of three items. For example, if the class which requires three items to be chosen has a total of ten items, the total number of permutations is 720.

This solution would transform the problem back into MCKP, but quickly becomes too resource intensive as the number of items in the special class increase. For example, 100 items in the special class would have 970,200 possible permutations.

So my question is: Is there a better way in which to conceptualize this problem? Has any research addressed this problem specifically?

• So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, \dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, \dots, C_{n1}, C_{n2}, C_{n3}$. – baudolino Apr 29 '13 at 3:32
• I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion. – Jester87 Apr 29 '13 at 4:56
• Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program. – baudolino Apr 29 '13 at 19:02
• Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one. – Jester87 Apr 30 '13 at 4:07

Maximize: $$\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}$$ Subject to: \begin{align} \sum _{i=1}^{n}\sum _{j=1}^{\left | G_{i} \right |}w_{ij}x_{ij} &\leq c \\ \sum _{j=1}^{\left | G_{i} \right |}x_{ij} &= 1 \\ \sum _{j=1}^{\left | G_{s} \right |}x_{sj} &= 3 \\ x_{ij} \in \{0,1\} \end{align} Notation:
G = {$G_{1},...,G_{n}$} the set of groups
${\left | G_{i} \right |}$ the number of items in group $G_{i}$
${\left | G_{s} \right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
• This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one). – baudolino May 1 '13 at 15:26