PHP Calculate balanced arrays

Well, I'm not sure if the name is effective, but this is the best I could come up with.

Basically there is a script.

I have 11 categories. In each category, I have elements, but one category can have 1 element, 1 can have 20.

Now I want to divide 11 categories into 5 stacks or columns.

I want each stack to contain an equal amount or an almost equal number of elements, and category elements cannot overflow the stack.

So, give 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 elements to be evenly distributed between the stacks.

There are 5 stacks to be equal, there must be 20 elements per stack. But there is a problem, elements 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 the stack is in if the elements are distributed most evenly between the stacks.

Now the results of calculating this stack will be cached, since I will not need to calculate very often, so if the solution is very difficult for the processor, publish it anyway.

Thanks:)

+4
source share
1 answer

This is a backpack problem. http://en.wikipedia.org/wiki/Knapsack_problem There are many resources - google ruble issue

One easy way is to try all possible combinations. In each combination that you calculate, you also calculate the standard deviation. Use standard deviation to maintain the best combination.

+1
source

All Articles