Algorithm to Divide a list of numbers into 2 equal sum lists
Dynamic programming is the solution you're looking for.
Example with [4, 3, 10, 3, 2, 5]:
X-Axis: Reachable sum of group. max = sum(all numbers) / 2 (rounded up)Y-Axis: Count elements in group. max = count numbers / 2 (rounded up) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | | 4| | | | | | | | | | | // 4 2 | | | | | | | | | | | | | | | 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | | | | | | | // 3 2 | | | | | | | 3| | | | | | | | 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 10 2 | | | | | | | 3| | | | | |10|10| 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 3 2 | | | | | | 3| 3| | | | | |10|10| 3 | | | | | | | | | | 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | 2| 3| 4| | | | | |10| | | | | // 2 2 | | | | | 2| 3| 3| | | | | 2|10|10| 3 | | | | | | | | 2| 2| 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | 2| 3| 4| 5| | | | |10| | | | | // 5 2 | | | | | 2| 3| 3| 5| 5| | | 2|10|10| 3 | | | | | | | | 2| 2| 3| 5| 5| | | ^
12 is our lucky number! Backtracing to get the group:
12 - 5 = 7 {5} 7 - 3 = 4 {5, 3} 4 - 4 = 0 {5, 3, 4}The other set can then be calculated: {4,3,10,3,2,5} - {5,3,4} = {10,3,2}
All fields with a number are possible solutions for one bag. Choose the one that is furthest in the bottom right corner.
BTW: It's called the knapsack-problem.
If all weights (w1, ..., wn and W) are nonnegative integers, the knapsack problem can be solved in pseudo-polynomial time using dynamic programming.
New Solution
This is a breadth-first search with heuristics culling. The tree is limited to a depth of players/2. The player sum limit is totalscores/2. With a player pool of 100, it took approximately 10 seconds to solve.
def team(t): iterations = range(2, len(t)/2+1) totalscore = sum(t) halftotalscore = totalscore/2.0 oldmoves = {} for p in t: people_left = t[:] people_left.remove(p) oldmoves[p] = people_left if iterations == []: solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys())) return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]]) for n in iterations: newmoves = {} for total, roster in oldmoves.iteritems(): for p in roster: people_left = roster[:] people_left.remove(p) newtotal = total+p if newtotal > halftotalscore: continue newmoves[newtotal] = people_left oldmoves = newmoves solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys())) return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])print team([90,200,100])print team([2,3,10,5,8,9,7,3,5,2])print team([1,1,1,1,1,1,1,1,1,9])print team([87,100,28,67,68,41,67,1])print team([1, 1, 50, 50, 50, 1000])#output#(200, 190, [90, 100])#(27, 27, [3, 9, 7, 3, 5])#(5, 13, [1, 1, 1, 1, 9])#(229, 230, [28, 67, 68, 67])#(150, 1002, [1, 1, 1000])Also note that I attempted to solve this using GS's description, but it is impossible to get enough information simply by storing the running totals. And if you stored both the number of items and totals, then it would be the same as this solution except you kept needless data. Because you only need to keep the n-1 and n iterations up to numplayers/2.
I had an old exhaustive one based on binomial coefficients (look in history). It solved the example problems of length 10 just fine, but then I saw that the competition had people of up to length 100.
Q. Given a multiset S of integers, is there a way to partition S into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2?
Best of luck approximating. : )