Add integers to a set number of lists, so that the sum of each completed list is as closely matching to the other lists as possible?

Question

I am trying to figure out how to solve this problem in computer science. I won't go into the programming side of things, but basically what I need is this:

I have a list of integers ranging from about 50 to 500 (these represent the height of elements on a web page I am building).

With these integers, I need to sort them into either 2, 3, 4, or 5 different lists (depending on the size of the users computer screen), but the problem is I need the sum of each list to match the sum of the other lists as closely as possible. So what I need is some way, mathematically, of working out which integers to add to each list, so that the sum of the integers in each list after all the integers have been added is as close as possible to every other list.

If someone could please tell me if this is possible, and if so, how I would go about it, I would be immensely grateful.

Thanks in advance

Cheers Corey

Answer 1

Here are just a few of my thoughts on a possible algorithm:

1. Find the sum of the whole list's values.
2. Divide this sum by the number of lists you need, from 2 to 5. This number is the one you want each list's individual sum to add up to.
3. If the number obtained in step 2 is an integer, great. If it isn't, find its remainder $R$ (achievable using '%' operator in JavaScript, for example) and store this number. Skip directly to step 7.
4. Add the largest number to the smallest, 2nd largest to the 2nd smallest... till the $n$th largest and $n$th smallest numbers, where $n$ is the number of lists you have.
5. Find the sum of each pair of numbers you added in step 4. Add to the one with the smallest total the largest number left from the original list.
6. Repeat step 5 until there are no more numbers left in the original list.
7. In the case the number wasn't an integer in step 2, this means that the number of items in each list won't be exactly even. Take out the smallest $R$ numbers from the original list, store them, and repeat the algorithm above as if there was no remainder. (So do steps 4 to 6).
8. Again, find the sum of each of the sub-lists and allocate the largest number from the remainder numbers you took out in step 7 to the sub-list with the smallest sum.
9. Repeat step 8 until there are no more remainder numbers left.

The subset sum and partition problems' programming solutions wouldn't really work here IMO since the chances of finding 2 - 5 sets, all mutually exclusive, totaling to the same number you found in 2. is minuscule.

I'm sorry for any possible confusion, this was a first thought and it includes a lot of referencing other steps which was unavoidable. This algorithm however should give you the closest approximation you can get to having all sums equal. In fact, if you want to see just how much of an error you obtained, subtract the sum of all the numbers in the original list from each of the sub-lists and average these numbers. This mean represents the average amount your lists are away from all having an equal sum. Depending on the distribution of values in your original list, the number might turn out to be relatively large (or small!). Hope for the latter.

Answer 2

I'd start like George D. by finding the target size of each list (sum of all elements divided by number of lists). Then I'd process the elements in reverse order of size (largest to smallest), at each step putting the current largest element into the most filled list in which it still fits under the target size.

For instance if my values were 500, 300, 250, 250, 175, 160, 100, and I wanted three lists, my target size would be $\frac{1735}{3}\approx 578.333$. My lists would develop as:

$[500]$

$[500], [300]$

$[500], [300, 250]$

$[500], [300, 250], [250]$

$[500], [300, 250], [250, 175]$

$[500], [300, 250], [250, 175, 160]$

$[500, 100], [300, 250], [250, 175, 160]$

Note: Your problem seems to fall into the category of 'bin-packing problems'. http://en.wikipedia.org/wiki/Bin_packing_problem