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 = 1
• C1 = 2
• C2 = 3
• C3 = 4

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.

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.