Packing problem

I have the following problem:

1. I have a given number of identically formed items with different colors (I know how many there are from each color)
2. I pack these items into boxes that can hold each a given number (n) of item in such way that I use the minimum number of boxes: round_up(total_nr_of_items/n)
3. There are some colors I am not allowed to put in one box except if I can't otherwise have the ideal number of boxes.
4. There is a minimal number of items from each color (different for each color) that I'm allowed to put开发者_运维百科 in a box. That is I can decide to put 0 pcs. of a color into a box or a minimum of k pcs. or above. This constraint can also be broken (as few times as possible) if the packing could not be done with the minimum number of boxes.
5. I want to find a solution where as few colors as possible are split between boxes.

I think this is a kind of packing problem but I don't know which one.

Please suggest into which packing problem can the above be converted into and/or an algorithm that I could use to solve this problem.

---

Looks like an NP-Hard constraint satisfaction problem. You'll have hard and soft constraints something like this.

Build-in constraints:

• I have a given number of identically formed items with different colors (I know how many there are from each color)

Hard constraints:

• There are some colors I am not allowed to put in one box.

• There is a minimal number of items from each color (different for each color) that I'm allowed to put in a box. That is I can decide to put 0 pcs. of a color into a box or a minimum of k pcs. or above.

Soft constraints:

• I pack these items into boxes that can hold each a given number (n) of item in such way that I use the minimum number of boxes: round_up(total_nr_of_items/n)

Softer constraints (or really low weight soft constraints):

• I want to find a solution where as few colors as possible are split between boxes.

For algorithms to solve this, take a look at Simulated annealing, Tabu search, Branch and bound, ...

For software which implements such algorithms and support constraints, take a look at Drools Planner (java, open source).

---

This could be NP-Hard.

The partition problem (for positive integers) seems to reduce to it.

Given an array of positive integers A[1,...n] of which we need to find some subset has the same sum as its complement.

Consider your colours to be 1 to n. You have two boxes. the minimum a box can hold for colour i is A[i] and you have exactly A[i] items of colour i.

The max number of items each box can hold is (A[1] + .. + A[n])/2.