Is this problem NP-hard?

Question

I am trying to find a reasonable algorithm for this problem:

Say you have a bunch of balls. Each ball has at least one color, but can also be multicolor. Each ball also has a number on it. There are also a bunch of boxes, each of which has only one color. The goal is to maximize the sum of the numbers on the balls in the boxes, and the only rules are:

• to put a ball in a box, it must have at least the color of the box on it
• You can only put one ball in each box.

For example, you can put a blue and green ball in a blue box or a green box, but not in a red frame.

I came up with several optimizations that help a lot in terms of run time. For example, you can sort the balls in descending order of the point value. Then, when you move from the highest to the lowest, if the ball has only one color, and there are no other balls with a higher point that contain this color, you can put it in this field (and thus remove this field and this ball from the rest of the combination).

I'm just curious if there is some kind of dynamic algorithm for this type of problem, or if it's just a traveling salesman problem in disguise. Would it help me if I knew that there are no more than X colors? Any help is appreciated. Thanks!

---

Edit is a simple example:

Balls:

• 1 red ball - 5 points.
• 1 blue ball - 3 points
• 1 green / red ball - 2 points.
• 1 green / blue ball - 4 points.
• 1 red / blue ball - 1 point

Boxes:

• 1 red
• 1 blue
• 1 green

Optimal solution:

• red ball in the red box
• blue ball in a blue box

• green / blue ball in a green box

  Total value: 12 points (5 + 3 + 4)

Answer 1

This is a special case of maximum weight matching on a weighted bipartite chart . Build a graph whose left vertices correspond to balls whose right vertices correspond to boxes and with an edge connecting a ball and a box having a weight V, where V is the number on the ball if the ball can be placed in the field, and 0 otherwise, Add extra boxes or balls connected to the other side with weight edges equal to zero until you have the same number of vertices on each side. The problem you are looking for is determined by the set of edges of nonzero weight in the maximum (total) weight matching in the resulting graph.

The assignment algorithm can be solved in O (n ^ 3) time, where n is the maximum number of balls or boxes using the Hungarian algorithm . (BTW, I have to make a disclaimer that I only mention the Hungarian algorithm, because this is a theoretical result that I happen to be familiar with, and it apparently answers the question in the title of whether the original problem is NP-hard be the best algorithm to use in practice.)

Answer 2

Have you tried greedy alg? Sort by points / value and put in the box if possible. If there are any exceptions, they do not have enough id to see them.