1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ As you formulated it, is seems that you can just take the n choices with the biggest values for each slot $\endgroup$
    – Ggouvine
    Commented Jun 5, 2020 at 11:54
  • $\begingroup$ 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 $\endgroup$
    – tomfroehle
    Commented Jun 5, 2020 at 19:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jun 5, 2020 at 21:32
  • 3
    $\begingroup$ Determining whether a solution exists at all is an instance of Set Cover. $\endgroup$
    – Yuval Filmus
    Commented Jun 5, 2020 at 21:35
  • $\begingroup$ Thank you D.W for your suggestion and thank you Yuval for your comment! $\endgroup$
    – tomfroehle
    Commented Jun 6, 2020 at 11:39

1 Answer 1

Reset to default
1
$\begingroup$

Thanks to Yuvals comment i found this site discussing the set cover problem. It's exactly what I needed.

Improve this answer
$\endgroup$

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.