An algorithm to sort a list of values into n groups so that the sum of each group is as close as possible

Question

Basically I have a number of values that I need to split into n different groups so that the sums of each group are as close as possible to the sums of the others? The list of values isn't terribly long so I could potentially just brute force it but I was wondering if anyone knows of a more efficient method of doing this. Thanks.

Answer 1

If an approximate solution is enough, then sort the numbers descendingly, loop over them and assign each number to the group with the smallest sum.

groups = [list() for i in range(NUM_GROUPS)]
for x in sorted(numbers, reverse=True):
    mingroup = groups[0]
    for g in groups:
        if sum(g) < sum(mingroup):
           mingroup = g
    mingroup.append(x)