Which algorithm can I use for distributing weighted objects equally in n portions?

Tag: algorithm Author: osik Date: 2009-08-11

I want to distribute x(i) objects (x E {1...n}), where each object has weight w(i), into n portions.

The distribution should be done in such a way, that for all the portions the sum of weights is as equal as possible.

Cheers! Pratik

Are you trying to minimize the maximum difference between any two portions, the average difference between the portions, or something else?

Best Answer

Calculate the total sum of the weights, divide by n the number of portions to get the required portion weight. Then use a bin packing algorithm (http://en.wikipedia.org/wiki/Bin%5Fpacking%5Fproblem) to try and fill n bins of this maximum size.

Note that all weights need to be less than the portion weight for this to work properly. Otherwise you won't be able to place the large weighted items anywhere.

comments:

a bit of preprocessing will take care of the corner case - find the required portion weight, remove any weights that are greater than the portion and put them into bins of their own, then run the bin packing algorithm for the remaining n-k weights and n-k bins.