将一组数字分成两个和相等的列表的算法

Question

有一串数字。
这串数字需要被分成两个大小相等的部分，并且这两个部分的总和要尽量接近。最后要把这两个部分的总和打印出来。

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

Answer 1

问：给定一个整数的多重集合 S，有没有办法把 S 分成两个子集 S1 和 S2，使得S1 中数字的总和等于S2 中数字的总和？

答：这就是所谓的集合划分问题。

祝你好运，试着去接近这个问题。: )

Answer 2

动态规划就是你要找的解决方案。

举个例子，假设我们有一组数字：[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}

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

顺便提一下，这个问题叫做背包问题。

如果所有的重量（w1, ..., wn 和 W）都是非负整数，那么背包问题可以通过动态规划在伪多项式时间内解决。

Answer 3

新方案

这是一个广度优先搜索的方法，结合了一些聪明的技巧来减少不必要的计算。这个树的深度限制在玩家数量的一半。玩家的总分限制是总分的一半。如果玩家池有100个人，解决这个问题大约需要10秒钟。

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])

另外，我还尝试过用GS的描述来解决这个问题，但仅仅通过存储运行总数是无法获得足够的信息的。如果你同时存储物品的数量和总分，那其实和这个方案是一样的，只是多存了一些没用的数据。因为你只需要保留前n-1和n的迭代，直到玩家数量的一半。

我之前有一个基于二项式系数的老方法（可以在历史记录中找到）。它能很好地解决长度为10的示例问题，但后来我发现比赛中有长度达到100的人。