Is this solvable in polynomial (or pseudo-polynomial) time?

Question

I'm trying to come up with a reasonable algorithm for this problem:

Let's say you have a bunch of balls. Each ball has at least one color, but can also be multicolored. Each ball has a weight and a value associated with it. There are also a bunch of boxes which are each only one color. Each box has a maximum number of balls it can hold. The goal is to maximize the sum of the value in the boxes while staying under some total weight, W, and the only rule is:

In order to place a ball in a box, it has to at least have the box's color on it

(For example, you can put a blue and green ball into a blue box or a green box, but not into a red box.)

I've dome some research and this seems similar to the knapsack problem and also similar to being solvable by the Hungarian algorithm, but I can't quite seem to reduce it to either problem.

I'm just curious is there's some kind of dynamic programming algorithm for this type of problem to make it solvable in polynomial time, or if it's just the traveling salesman problem in disguise. Would it help if I knew there were at most X colors? Any help is greatly appreciated. I could also formalize the problem a bit with variable names if it would help. Thanks!

Here's a simple example:

Maximum weight: 5

Balls:

1 red ball - (value = 5, weight = 1)

1 blue ball - (value = 3, weight = 1)

1 green/red/blue ball - (value = 2, weight = 4)

1 green/blue ball - (value = 4, weight = 1)

1 red/blue ball - (value = 1, weight = 1)

Boxes:

1 red (holds 1 ball)

1 blue (holds 2 balls)

1 green (holds 1 ball)

Optimal Solution:

red ball in red box

blue ball and red/blue ball in blue box

green/blue ball in green box

Total value: 13 (5 + 3 + 1 + 4)

Total weight: 4 (1 + 1 + 1 + 1)

Note: even though the green/red/blue ball was more valuable than the red/blue ball, it's weight would have put us over the limit.

Edit:

One clarifying point: balls with the same color combination will not necessarily have the same weights and values. For example, you could have a red ball with value 3 and weight 1 and another red ball with value 2 and weight 5.

Edit 2:

We can assume integer weights and values if it helps us come up with a dynamic programming algorithm.

Answer 1

This is at least as complex as the Knapsack problem - consider a case where all balls are red and there is only one red box.

In the case when balls that have the same combination of colors must have the same weights and values consider a case when you have red/blue, red/green, etc. balls and only one red box.

Answer 2

If there is no bound on the number of boxes, then this problem is strongly NP-hard by reduction from 3-partition (set up n/3 boxes and make all the things rainbow-colored with value = weight).

If the number of boxes is constant, then there's a pseudo-polynomial time algorithm via dynamic programming, where each DP state consists of how full each box is.