メソッドが機能しないテストケースは
que = [1, 1, 50, 50, 50, 1000]
問題は、物事をペアで分析していることです。この例では、すべての 50 代を同じグループに入れたいと考えています。ただし、ペア分析の側面を削除して、一度に 1 つのエントリだけを実行すると、これは解決されるはずです。
これを行うコードは次のとおりです
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]私の方法が機能しない理由は明らかです。具体的には、この例を解くには、有効な解を得るために 2 つの最大数を両方とも同じ数列に追加する必要があります。
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