Тестовый пример, где ваш метод не работает:
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