python - 从列表中删除数字而不更改总和

Question

我有一个数字列表(例如:[-1, 1, -4, 5])，我必须从列表中删除数字而不改变列表的总和。我想删除可能具有最大绝对值的数字，而不更改总数，在示例中删除 [-1, -4, 5] 将留下 [1] 所以总和不变。

我写了一种朴素的方法，即找出所有不会改变总数的可能组合，然后看看哪一个消除了最大的绝对值。但这真的很慢，因为实际列表会比这大得多。

这是我的组合代码:

from itertools import chain, combinations

def remove(items):
    all_comb = chain.from_iterable(combinations(items, n+1) 
                                   for n in xrange(len(items)))
    biggest = None
    biggest_sum = 0
    for comb in all_comb:
        if sum(comb) != 0:
            continue # this comb would change total, skip
        abs_sum = sum(abs(item) for item in comb)
        if abs_sum > biggest_sum:
            biggest = comb
            biggest_sum = abs_sum
    return biggest

print remove([-1, 1, -4, 5])

它正确地打印了 (-1, -4, 5)。然而，我正在寻找一些比遍历所有可能的项目组合更聪明、更有效的解决方案。

有什么想法吗？

Answer 1

如果您将问题重新定义为寻找总和等于完整集值的子集，您将意识到这是一个 NP-Hard 问题，(subset sum)

所以这个问题没有多项式复杂度解。