# Find the n best choices while maximizing value

Given:

• A list of slots (A, B, C, ...)
• Every slots supports a list of choices (C0, C1, C2, C3...)
• Every choice has a value

All slots must be filled with at most n different choices. The sum of the values should be maximized.

Example:

Choice-Values:

• C0 = 4
• C1 = 3
• C2 = 2
• C3 = 1

Slots:

• A: C1, C3
• B: C0, C1, C3
• C: C2, C3
• D: C0, C1, C2, C3
• E: C1, C2, C3

Solution for n = 1: C3, C3, C3, C3, C3

Solution for n = 2: C1, C1, C2, C1, C1

Question

Is this a known problem?

It reminds me of a mix between the knapsack problem and of a scheduling problem, as I want to get the maximum value while filling a certain space using a limited set of items.

• As you formulated it, is seems that you can just take the n choices with the biggest values for each slot Jun 5, 2020 at 11:54
• Then I have to rephrase it: Let's say I have 10 slots. For every slot there are a different number of possible choices. Now I want to find the n = 3 choices that cover all slots and have the maximum value. I want to use at most 3 different choices for all slots Jun 5, 2020 at 19:47
• If you'd like to change the problem, please edit the question so it reflects the new problem. Don't just post a comment -- change the question so it matches what you want to ask, and so it reads well for someone who encounters this for the first time. Usually it's more useful to ask what you want to know (e.g., for an efficient algorithm) rather than if it is a known problem. That way you have two ways to win: either someone tells you it is a known algorithm and where to find the answer, or they answer it even if it isn't a known problem.
– D.W.
Jun 5, 2020 at 21:32
• Determining whether a solution exists at all is an instance of Set Cover. Jun 5, 2020 at 21:35
• Thank you D.W for your suggestion and thank you Yuval for your comment! Jun 6, 2020 at 11:39