一个您的方法无法正常工作的测试用例是:
que = [1, 1, 50, 50, 50, 1000]
问题在于你正在以成对的方式分析事物,而在这个例子中,你希望所有的50都在同一组中。如果你删除成对分析方面,只是逐个输入,这个问题就可以解决了。
以下是实现此操作的代码。
def make_teams(que):
que.sort()
que.reverse()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
if abs(len(t1)-len(t2))>=len(que):
[t1, t2][len(t1)>len(t2)].append(que.pop(0))
else:
[t1, t2][sum(t1)>sum(t2)].append(que.pop(0))
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
if __name__=="__main__":
que = [2,3,10,5,8,9,7,3,5,2]
make_teams(que)
que = [1, 1, 50, 50, 50, 1000]
make_teams(que)
这给出了27、27和150、1002,这些答案对我来说是有意义的。
编辑:经过审查,我发现这实际上并不起作用,但最终,我不太确定为什么。 我将在此处发布我的测试代码,因为它可能很有用。 测试只是生成具有相等总和的随机序列,将它们放在一起并进行比较(结果很糟糕)。
编辑#2:根据Unknown指出的示例[87,100,28,67,68,41,67,1]
,很明显我的方法不起作用。 具体而言,要解决此示例,需要将两个最大的数字都添加到同一个序列中才能获得有效的解决方案。
def make_sequence():
"""return the sums and the sequence that's devided to make this sum"""
while 1:
seq_len = randint(5, 200)
seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
seqs = [[], []]
for i in range(seq_len):
for j in (0, 1):
seqs[j].append(randint(1, seq_max))
diff = sum(seqs[0])-sum(seqs[1])
if abs(diff)>=seq_max:
continue
if diff<0:
seqs[0][-1] += -diff
else:
seqs[1][-1] += diff
return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]
if __name__=="__main__":
for i in range(10):
s0, s1, seq0, seq1 = make_sequence()
t0, t1 = make_teams(seq0+seq1)
print s0, s1, t0, t1
if s0 != t0 or s1 != t1:
print "FAILURE", s0, s1, t0, t1