PHP Calculate Balanced Arrays

Question

Ok, I'm not sure if the title is that effective but its the best I could come up with.

Basically here is the scenario.

I have 11 categories. In each category, I have items, but one category might have 1 item, 1 might have 20.

Now i want to separate the 11 categories into 5 stacks or columns.

I want each of the stacks to contain an equal amount or almost equal amount of items and no categories items can overflow a stack.

So given the following data:

Category | Items
-------------------------
Cat 1 | 10 
Cat 2 | 3 
Cat 3 | 7 
Cat 4 | 11 
Cat 5 | 5 
Cat 6 | 13
Cat 7 | 19 
Cat 8 | 5  
Cat 9 | 3 
Cat 10 | 9 
Cat 10 | 15

Total = 100 Items

So i want the items to be spread evenly among the stacks.

There are 5 stacks so to be equal there should be 20 items per stack. But there is the problem, items from 1 stack cannot overflow. So how can i calculate the data to output something like this:

Stack 1|Stack 2|Stack 3|Stack 4|Stack 5
-------|-------|-------|-------|-------
Cat 10 |Cat 1  |Cat 11 |Cat 6  |Cat 7
Cat 4  |Cat 3  |Cat 8  |Cat 9  |
       |Cat 2  |       |Cat 5  |

20      20      20      21      19

It doesn't matter what category is in which stack as long as the items are spread the most evenly among the stacks.

Now the results of this stack calculation will be cached as I wont need to calculate very often so if the solution is very CPU heavy, still post it.

Thanks :)

Answer 1

This is a knapsack problem. http://en.wikipedia.org/wiki/Knapsack%5Fproblem There are many resources is you google knapsack problem

One simple way is to try all the possible combinations. Each combination you calculate you would also calculate the Standard deviation. Use the Standard deviation to save the best fitting combination.