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.

$\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$ – Gabriel Gouvine Jun 5 '20 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 Jun 5 '20 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. Jun 5 '20 at 21:32
  • 3
    $\begingroup$ Determining whether a solution exists at all is an instance of Set Cover. $\endgroup$ – Yuval Filmus Jun 5 '20 at 21:35
  • $\begingroup$ Thank you D.W for your suggestion and thank you Yuval for your comment! $\endgroup$ – tomfroehle Jun 6 '20 at 11:39
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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