0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Each item has only one color or can be multiple-colored? $\endgroup$
    – rus9384
    Commented Sep 11, 2017 at 22:05
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Sep 12, 2017 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Sep 12, 2017 at 15:10

2 Answers 2

Reset to default
2
$\begingroup$

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.

This is the answer.

Improve this answer
$\endgroup$
0
$\begingroup$

Trying all combinations of k colors must be doable in O(n^k+1) time, isn't it?

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).

Each item has only one color or can be multiple-colored?

Yes, each item has only one color and thank you very much for your excellent answer. That's what I was looking for!

PS. I am still figuring out my way around the forum so I don't know yet how to reply directly.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Try using LaTeX to make your answer more readable. For example, kCC is rather hard to parse. $\endgroup$
    – Yuval Filmus
    Commented Sep 12, 2017 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.