将数字列表分为 2 个等和列表的算法

有一个数字列表。
该列表将被分为 2 个大小相等的列表，并且总和相差最小。金额必须打印出来。

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

对于某些情况，以下代码算法是否存在错误？

我如何优化和/或Python化这个？

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"

问题来自http://www.codechef.com/problems/TEAMSEL/ http://www.codechef.com/problems/TEAMSEL/

动态规划 http://en.wikipedia.org/wiki/Dynamic_programming是您正在寻找的解决方案。

[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是你的幸运数字！回溯得到该组：

12 - 5 = 7        {5}
 7 - 3 = 4        {5, 3}
 4 - 4 = 0        {5, 3, 4}
  

然后可以计算另一组：{4,3,10,3,2,5} - {5,3,4} = {10,3,2}

所有带有数字的字段都是一个包的可能解决方案。选择右下角最远的一个。

顺便说一句：这就是所谓的背包问题 http://en.wikipedia.org/wiki/Knapsack_problem.

如果所有权重（w1，...，wn 和 W）都是 非负整数，背包 问题可以解决 使用动态伪多项式时间 编程。