Algorithm to allocate a list of numbers to N groups under certain condition

Question

Let's say I have a list of numbers:

2,2,3,4,4

Split the numbers into N groups (3 groups here as an example):

A:2,3 sum:5

B:4 sum:4

C:2,4 sum:6

What I want is to minimize (the group with the highest sum (6 here) - the group with the smallest sum (4 here))

Does anyone think of an algorithm to achieve this?

Another example:

7,7,8,8,8,9,9,10

The result should be as follows:

A:7,8,8 sum:23

B:7,8,9 sum:24

C:9,10 sum:19

Answer 1

Considering that even if N is two the problem is NP complete, I can give you a very bad algorithm.

http://mathworld.wolfram.com/NumberPartitioningProblem.html

Answer 2

Unfortunately, this problem is NP hard. See references for multiprocessor scheduling or bin packing. You may also be able to find some useful approximation algorithms, if you're interested in that approach.

Answer 3

Zweiterlinde's suggestion to check out bin packing is the way to go.

I went ahead and posted this, having realized it was wrong after I had typed it all.

You want a greedy approach where the largest numbers are used first.

1. sort the list to achieve an ordering
2. Begin placing the largest numbers into groups -- as many as will fit to reach the first number
3. Stop when max number of groups is reached
4. Sort your groups by sum and repeat by adding the largest number to the smallest group, repeating until done.

This should get you: from 2,2,3,4,4 ...

group 1 (4): 4
group 2 (6): 4, 2
group 3 (5): 3, 2

and from 7,7,8,8,8,9,9,10 ...

group 1 (18): 10, 8
group 2 (24): 9, 8, 7
group 3 (24): 9, 8, 7

Though I guess the second example could be done as 19, 24, 23 which makes this wrong. Hmph.