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/
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.