# Is a Knapsack Problem with only Color Constraints NP-Complete?

I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors.

There exists a constraint on the number of different colors of objects in the knapsack (but no "weight" constraint), and the goal is to maximize the value of the knapsack.

It's basically the same setting as in this model http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.9533&rep=rep1&type=pdf except that there is only one knapsack and the items are "weightless".

Is this problem hard, easy, yet to be classified? I would really appreciate any pointers. Please and thank you in advance.

• Each item has only one color or can be multiple-colored? Sep 11, 2017 at 22:05
• Please don't edit the question to ask follow-up questions or try to conduct a discussion. Discussions and back-and-forths are discouraged here. If you have a follow-up question, please ask it separately using the 'Ask Question' button in the upper right (but make sure to make it self-contained). Also please ask only one question per post. I have deleted the follow-up question, but you can view the revision history (click 'edited') to see the old material for use with copy-paste.
– D.W.
Sep 12, 2017 at 15:09
• It looks like you've accidentally created multiple accounts. I encourage you to merge them and register the account to ensure you retain access and ability to edit your question and post comments.
– D.W.
Sep 12, 2017 at 15:10

So, items have only 2 parameters:

1. Color. I assume that each item has one color ("one of C colors"). If not, this problem is probably $\mathsf{NP}$-hard.
2. Price.

Now we need to pack a knapsack to maximize the price. Knapsack can have at most $k$ colors.

Algorithm:

1. For each color count the total price of items that are colored by color $C_i$. Call these values $P_i$. Takes linear time.
2. Find $k$ maximal values of $P$. Takes polynomial (linear?) time. Can be done using sorting.

No, I think that would be factorial in C. There are ${C}\choose{k}$ different combinations of k colors (the number of subsets of k colors to choose from a set of C colors).