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

Question

我有这种背包的变体，几乎没有限制，没有限制让我真的不知道从哪里开始。

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

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

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

Answer 1

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

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

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

Python中的示例使用二进制算术来存储集合（位i+1对应于使用i-th项求和）。 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] and [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}

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

knapsack problem variation with almost no constraints

algorithm

knapsack-problem

dynamic-programming