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

小编典典

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

algorithm

有一个数字列表。

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

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

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

如何优化和/或pythonize？

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/

阅读 267

2020-07-28

共1个答案

小编典典

新解决方案

这是启发式剔除的广度优先搜索。该树限于玩家的深度/ 2。玩家总和限制为totalscores / 2。玩家人数为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次迭代保持为numplayers / 2。

我有一个基于二项式系数的旧式详尽清单（历史记录）。它很好地解决了长度为10的示例问题，但后来我看到比赛的人数不超过100。

2020-07-28