python - 平衡两个列表，直到它们的总和相等，并且在 Python 中的两个列表中交换最小

Question

a = [70, 30, 33, 23, 4, 4, 34, 95]
b = [50, 10, 10, 7]

我已经试过了，但我知道这不够准确

if sum(a) > sum(b):
   a.sort()
   b.sort()
   temp = [int(i) for i in a]
   i=0
   while(sum(b) <= sum(temp)  and (i <= len(a) - 1)):
      b.append(a[i])
      temp.remove(a[i])
      i = i+1

    a = [int(i) for i in temp]
if sum(b) > sum(a):
    a.sort()
    b.sort()
    temp = [int(i) for i in b]
    i=0
    while(sum(a) <= sum(temp)  and (i <= len(b) - 1)):
        a.append(b[i])
        temp.remove(b[i])
        i = i+1        

    b = [int(i) for i in temp]

结果是:

总和 = 186, 184

列表 = [7, 10, 70, 95, 4], [4, 10, 23, 30, 33, 34, 50]

必填答案:

总和 = 185, 185

列表 = [7, 10, 23, 50, 95], [4, 4, 10, 30, 33, 34, 70]

Answer 1

您要解决的问题称为子集求和问题并且是 NP 完全问题，因此您不会比蛮力搜索好多少。

这至少提供了一个使用蛮力的解决方案:

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def lst_difference(lst, other):
    s = list(lst)
    for el in other:
        s.remove(el)
    return s

a = [70, 30, 33, 23, 4, 4, 34, 95]
b = [50, 10, 10, 7]

lst = a + b
total = sum(lst)

for subset in powerset(lst):
    if sum(subset) == total // 2:
        other_subset = lst_difference(lst, subset)

        print('subset1 = {}, subset2 = {}'.format(subset, other_subset))

它给出了这些解决方案:

subset1 = (70, 95, 10, 10), subset2 = [30, 33, 23, 4, 4, 34, 50, 7]
subset1 = (30, 95, 50, 10), subset2 = [70, 33, 23, 4, 4, 34, 10, 7]
subset1 = (30, 95, 50, 10), subset2 = [70, 33, 23, 4, 4, 34, 10, 7]
subset1 = (33, 23, 34, 95), subset2 = [70, 30, 4, 4, 50, 10, 10, 7]
subset1 = (33, 95, 50, 7), subset2 = [70, 30, 23, 4, 4, 34, 10, 10]
subset1 = (30, 33, 23, 4, 95), subset2 = [70, 4, 34, 50, 10, 10, 7]
subset1 = (30, 33, 23, 4, 95), subset2 = [70, 4, 34, 50, 10, 10, 7]
subset1 = (23, 95, 50, 10, 7), subset2 = [70, 30, 33, 4, 4, 34, 10]
subset1 = (23, 95, 50, 10, 7), subset2 = [70, 30, 33, 4, 4, 34, 10]
subset1 = (70, 23, 4, 4, 34, 50), subset2 = [30, 33, 95, 10, 10, 7]
subset1 = (30, 33, 95, 10, 10, 7), subset2 = [70, 23, 4, 4, 34, 50]
subset1 = (70, 30, 33, 4, 4, 34, 10), subset2 = [23, 95, 50, 10, 7]
subset1 = (70, 30, 33, 4, 4, 34, 10), subset2 = [23, 95, 50, 10, 7]
subset1 = (70, 4, 34, 50, 10, 10, 7), subset2 = [30, 33, 23, 4, 95]
subset1 = (70, 4, 34, 50, 10, 10, 7), subset2 = [30, 33, 23, 4, 95]
subset1 = (70, 30, 23, 4, 4, 34, 10, 10), subset2 = [33, 95, 50, 7]
subset1 = (70, 30, 4, 4, 50, 10, 10, 7), subset2 = [33, 23, 34, 95]
subset1 = (70, 33, 23, 4, 4, 34, 10, 7), subset2 = [30, 95, 50, 10]
subset1 = (70, 33, 23, 4, 4, 34, 10, 7), subset2 = [30, 95, 50, 10]
subset1 = (30, 33, 23, 4, 4, 34, 50, 7), subset2 = [70, 95, 10, 10]