algorithm - 几乎没有约束的背包问题变体

Question

我有这种背包的变体，几乎没有约束，而缺乏约束让我真的不知道从哪里开始。

给定一组正整数 S。可能: 1 2 3 4 5 6 7 8 9 10 11 12 13

找到两个不重叠且总数相同的子集。这两个集合不需要包含 S 中的所有数字。 所以对于前一个例子，答案是 [1,2]和[3]

通常这些问题都有一些约束，例如子集需要具有特定的总和，或者子集需要跨越 S 的所有元素。 这让我很难想象如何通过暴力破解来解决这个问题。每次我想出一个动态规划表时，我都无法让它涵盖子集的所有可能排列

Answer 1

这个问题可以像伪多项式时间内的子集和问题一样解决O(n*summ)

我们用可能的子集总和填充数组0..summ，当我们遇到相同的总和时 - 我们停止。

两个相等的和可能由一些相同的项组成 - 我们只是删除它们，因此其余的和仅包含不同的项。

Python 中使用二进制算术存储集合的示例(位 i+1 对应于使用总和中的第 i 项)。 common 包含相同的位，我们使用异或运算删除它们。

最后几行自行检索所需的集。

L = [2,5,11,17,29,37,43]
summ = sum(L)
A =[0]*(summ+1)
A[0] = 1

X = 0
Y = 0
for i in range(len(L)):
    for k in range(summ, L[i] - 1, -1):
        if A[k - L[i]]:
            t = A[k - L[i]] | (2 << i)
            if A[k]:
                common = A[k] & t
                X = A[k] ^ common
                Y = t ^ common
                break
            else:
                A[k] = t
    if X:
        break

first = [L[i] for i in range(len(L)) if (X & (2 << i))]
second = [L[i] for i in range(len(L)) if (Y & (2 << i))]
print(first, second)

>>> [2, 11, 29] [5, 37]

在此示例中，代码找到 [2, 11, 17, 29] 和 [5, 17, 37] 的和 59 相等，并删除常见的 17 得到总和 42

的最终结果

---

不必将集合存储在 A[] 单元格中 - 我们可以存储总和的最后一项，然后展开项目序列

L = [2,5,11,17,29,37,43]
summ = sum(L)
A =[0]*(summ+1)
A[0] = -1
last = 0
for i in range(len(L)):
    for k in range(summ, L[i] - 1, -1):
        if A[k - L[i]]:
            t = L[i]
            if A[k]:
                last = k
                break
            else:
                A[k] = t
    if last:
        break

first = set()
k = last
while k:
    first.add(A[k])
    k = k - A[k]

second = set()
second.add(t)
k = last - t
while k:
    second.add(A[k])
    k = k - A[k]

print(first.difference(second),second.difference(first))

>>> {2, 11, 29} {37, 5}