Bin packing - variants and quantities across a known number of unique boxes

Question

I have a head-scratcher which feels similar to a classic bin packing problem, but I can't pin it down. Any help appreciated...

Problem:

I have a set of products that are all the same size, but there are differently coloured variants and different requested quantities of each making up an order.

I am allowed to pack them in any combinations, but I can only have a stipulated number of boxes with different contents.

I can supply different quantities of each box. The optimal solution is the one which has the fewest number of products shipped above the requested quantity.

EXAMPLE: 4 products fit in a box, I'm allowed 2 types of box with different contents and I need to ship 100 * Red, 200 * Blue, 300 * Green, 400 * Yellow;

I can't pack 25 boxes of red, 50 boxes of blue, 75 boxes of green and 100 boxes of yellow because I'm only allowed 2 different unique contents of the boxes, and this would be 4.

Therefore optimal solution would be:

100 boxes of 1 * Red, 2 * Blue and 1 * Yellow

150 boxes of 2 * Green and 2 * Yellow

I've fulfilled all my quantities exactly in this example, so there is zero waste.

Let's say the order only requires 395 yellow; the above solution will waste 5 yellows, but there is no solution which wastes fewer. The solution with the fewest wasted products is the best.

Answer 1

Caution: Not an algorithmic answer.

Use brute force.

Given the types, you could (fairly) easily check how much waste you would get.

Since in each type you can have only 4 items, and there are only two types, the number of different options here is (4^4)^2 (based on x=number_of_colours, y=number_of_items_in_type and z=number_of_types, we have (x^y)^z).

So why not check all 65536 options? Most of them are easily disqualified (every colour has to be represents at least once, etc.)

EDIT: Since the numbers of the real problem are far greater than the example, this answer is no longer relevant. I am leaving it here in case a better idea creeps up.