总数集（也为负），总和等于0

Question

我有一组庞大的数字，并有定义的顺序。用简单的术语逻辑看起来就是这样：

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

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

预期= 0

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

解决方案['values'] = [1,1,3,4，-9]

解决方案['order'] = [1,2,3,4,6]

该总和也可以通过用第五次替换第4阶数字来实现但是，订单编号是一个最佳解决方案就足够了。目标是达到总和= 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开始，只需更改枚举如下

Answer 2

也许我缺少一些东西（已经很晚了），但是如果我们用k元素表示子集，则为s（k），并且我们有n总共可以：您可以：

• 查看s（n）是否总和为0;如果是这样，那是最大的子集
• ，如果没有，请查看s（n-1）是否总和为0； 如果没有，则有n这样的集合
• ，请查看s（n-2） dim dim;有n*（n-1）这样的集合

等。这是一种“蛮力”解决方案，可能远非最佳，但是如果最大的子集有望相对较大（大小接近n），那就不错了。请注意，每个步骤都可以利用前面步骤中计算的总和。

您的解决方案[order]似乎是解决方案子集的索引。当然可以做到这一点，但是我不确定为什么您需要获得值及其索引？有点多余。

最后，尽管在纯Python中可行，但Numpy库可能对这种问题有用。