python - 总和等于 0 的数字集(也为负数)中最大的子集

Question

我有一大堆具有明确顺序的数字。简单来说，逻辑如下:

data['values'] = [1,1,3,4,4,-9,10]

data['order'] = [1,2,3,4,5,6,7]

ExpectedSum = 0

我希望返回的是原始顺序和我们可以获得的总和等于 0 的值的最大可能子集的值。对于这种情况，一个最佳解决方案是

solution['values'] = [1,1,3,4,-9]

solution['order'] = [1,2,3,4,6]

也可以通过将第4阶数替换为第5阶数来实现求和，但是，一个最优解就足够了。目标是达到总和 =0 的子集的最大可能大小。

正在寻找背包问题和最大子数组算法的变体，但没有一个满足我的需求。

任何提示或指示表示赞赏。

Answer 1

所有固定长度的子集都可以通过“n 选择 k”的方式找到。为了找到最长的迭代，从 k=n 开始，然后减一。

import itertools as it

def combination_finder(l: list) -> tuple:
    for i in range(len(l)):
        for pairs in it.combinations(enumerate(l, start=0), len(l)-i):
            i, c = zip(*pairs)
            if sum(c) == 0:
                return i, c
    
    raise Exception('No combination found.')

l = [1,1,3,4,4,-9,10]
id_, comb = combination_finder(l)
print(id_)
print(comb)

备注:要使id_从1开始，只需将enumerate更改为enumerate(l, start=1)