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

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问题,(子集和)

所以这个问题没有多项式复杂性解决方案.