0-1 Knapsack with additional restriction (colored

问题:

I'm working on this problem mostly out of curiosity in my downtime at work.

Imagine the normal 0-1 Knapsack problem, except all the items are either yellow, red, blue, or green, and due to your OCD you must have exactly 2 items of each color in your knapsack. So instead of the normal items each item has 3 properties: Weight, Value, Color.

Is this even still a knapsack problem, or is it better define in some other way?

回答1:

I'll use nCk to represent "n choose k" for ease of typing. Since you must have exactly 2 items of each color, the number of feasible solutions is O(nC2), which is O(n^2). Each solution can be evaluated in polynomial time, so the problem is solvable in polynomial time as well. In other words, it's far simpler than a regular knapsack problem.