如何将一个负数和正数列表划分为总数为0的最大子集？

Question

bounty到期在7天内。该问题的答案有资格获得+ 50声望赏金。reuseman希望引起更多关注对此问题：

我想要算法的伪代码实现

我正在尝试解决此问题，但我无法设法解决。

假设我有一个正负数列表，它们的和保证为0。

[-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]                  

我想使用初始列表的所有元素仅获取一次子集最多的列表。并且每个子集的总和必须为0。

因此，在此简单输入的情况下：

[-5, -4, 5, 2, 3, -1]

可获得的最佳结果是：

1. [[-5, 5], [[-4, -1, 2, 3]]]   #2 subsets
2. [[-5, 2, 3], [-4, -1, 5]]     #2 subsets

例如，这些完全是错误答案：

1. [[-5, -4, -1, 2, 3, 5]]       #1 subsets that is the initial list, NO
2. [[-5,5]]                      #1 subset, and not all elements are used, NO

即使它是NP-Complete，即使采用蛮力方法，我也如何设法解决它？我只需要一小部分数字的解决方案。

Answer 1

def get_subsets(lst):
    N = len(lst)
    cand = []
    dp = [0 for x in range(1<<N)]   # maximum number of subsets using elements represented by bitset
    back = [0 for x in range(1<<N)]

    # Section 1
    for i in range(1,1<<N):
        cur = 0
        for j in range(N):
            if i&(1<<j):
                cur += lst[j]
        if not cur:
            cand.append(i)     # if subset sums to 0, it's viable
    dp[0] = 1

    # Section 2
    for i in range(1<<N):
        while cand and cand[0] <= i:
            cand.pop(0)
        if not dp[i]:
            continue
        for j in cand:
            if i&j:     # if subsets intersect, it cannot be added
                continue
            if dp[i]+1 > dp[i|j]:
                back[i|j] = j
                dp[i|j] = dp[i]+1

    # Section 3
    ind = dp.index(max(dp))
    res = []

    while back[ind]:
        cur = []
        for i in range(N):
            if back[ind]&(1<<i):
                cur.append(lst[i])
        res.append(cur)
        ind = ind^back[ind]

    return res

print (get_subsets([-5, -4, 5, 2, 3, -1]))

Answer 2

本质上与Michael Huang相同，下面还有30行...