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?