Algorithm to Divide a list of numbers into 2 equal sum lists

Question

There is a list of numbers.
The list is to be divided into 2 equal sized lists, with a minimal difference in sum. The sums have to be printed.

#Example: >>>que = [2,3,10,5,8,9,7,3,5,2] >>>make_teams(que) 27 27 

Is there an error in the following code algorithm for some case?

How do I optimize and/or pythonize this?

def make_teams(que):     que.sort()     if len(que)%2: que.insert(0,0)     t1,t2 = [],[]     while que:         val = (que.pop(), que.pop())         if sum(t1)>sum(t2):             t2.append(val[0])             t1.append(val[1])         else:             t1.append(val[0])             t2.append(val[1])     print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n" 

Question is from http://www.codechef.com/problems/TEAMSEL/

Answer 1

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.

Answer 2

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.