总和等于 0 的一组数字（也是负数）的最大子集

Question

我有一大堆数字，它们的顺序是固定的。简单来说，逻辑如下所示：

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

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

ExpectedSum = 0

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

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

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

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

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

感谢任何提示或指示。

Answer 1

也许我遗漏了什么（已经晚了），但是如果我们将具有 k 个元素的子集表示为 S(k) 并且我们总共有 N 个元素，您可以:

看看S(N)是否和为0；如果是这样，那就是最大的子集
如果不是，看S(N-1)中有没有和为0；有N个这样的集合
如果没有，请查看 S(N-2) 是否有；有N*(N-1)个这样的集合

等等。这是一个“蛮力”解决方案，可能远非最佳，但如果预计最大子集相对较大（大小接近 N），它应该不会太糟糕。请注意，每一步都可以利用前一步计算的总和。

您的 solution[order] 似乎是解决方案子集的索引。当然可以做到，但我不确定为什么你需要同时获得这些值和它们的索引？有点多余。

最后，虽然在纯 Python 中可行，但 NumPy 库可能对此类问题有用。

Answer 2

所有固定长度的子集都可以用“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)

总和等于 0 的一组数字（也是负数）的最大子集

Largest subset from set of numbers (also negative) having sum equal 0

python

algorithm

math

pseudocode

dynamic-programming