如何将一个负数和正数的列表划分为最大数量的和为0的子集？
How to divide a list of negative and positive numbers into the largest number of subsets whose sum is 0?
我正在尝试解决这个问题，但我不知道如何解决。
假设我有一个正数和负数的列表，其和保证为 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，即使使用蛮力方法我如何设法解决它？我只需要一个小数字列表的解决方案。
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]))
基本上，此解决方案会收集原始列表中总和为零的所有子集，然后尝试将尽可能多的子集合并在一起而不会发生冲突。它在最坏情况下为 运行s O(2^{2N}) 时间，其中 N 是列表的长度，但它应该达到大约 O(2^N) 的平均情况，因为通常应该总和为 0 的子集太多了。
编辑：我添加了部分以便于解释算法
第 1 部分：我遍历原始列表的所有可能的 2^N-1 个非空子集，并检查这些子集中哪些子集的和为 0；任何可行的零和子集都被添加到列表 cand（表示为 [1,2^N-1] 范围内的整数，并在构成子集的索引处设置位）。
第 2 部分：dp 是一个动态规划 table 存储总和为 0 的子集的最大数量，这些子集可以使用整数 i 表示的子集在 dp[i]。最初，dp 的所有条目都设置为 0，除了 dp[0] = 1，因为空集的总和为 0。然后我从 0 到 2^N-1 遍历每个子集，并且我 运行遍历候选子集列表并尝试合并两个子集。
第3节：这只是回溯寻找答案：在填写dp时，我还保留了一个数组back，用于存储最近添加的子集以实现子集[=13] =] 在 back[i]。所以我找到了最大化子集数的子集，总和为 0 ind = dp.index(max(dp))，然后我从那里回溯，通过删除最近添加的子集来缩小子集，直到我最终回到空集。
下面和Michael Huang基本一样的思路，多了30行...
有小集团的解决方案
我们可以预构建所有总和为0的子集
- 构建 1 个元素的子集；
- 然后通过重复使用之前的大小 2
- 并保留那些总和为零的人
现在说这样的子集是图的一个节点。
然后一个节点与另一个节点相关，前提是它们的关联子集没有共同的数字。
因此我们要构建图的最大团：
- 在一个集团中，所有节点都具有相同的关系，它们的子集是不相交的
- 最大团给了我们最大数量的子集
function forall (v, reduce) {
const nexts = v.map((el, i) => ({ v: [el], i, s: el })).reverse()
while (nexts.length) {
const next = nexts.pop()
for (let i = next.i + 1; i < v.length; ++i) {
const { s, skip } = reduce(next, v[i])
if (!skip) {
nexts.push({ v: next.v.concat(v[i]), s: s, i })
}
}
}
}
function buildSubsets (numbers) {
const sums = []
forall(numbers, (next, el) => {
const s = next.s + el
if (s === 0) {
sums.push({ s, v: next.v.concat(el) })
return { s, skip: true }
}
return { s }
})
return sums
}
const bin2decs = bin => {
const v = []
const s = bin.toString(2)
for (let i = 0; i < s.length; ++i) {
if (intersects(dec2bin(i), bin)) {
v.push(i)
}
}
return v
}
const dec2bin = dec => Math.pow(2, dec)
const decs2bin = decs => decs.reduce((bin, dec) => union(dec2bin(dec), bin), 0)
// Set methods on int
const isIn = (a, b) => (a & b) === a
const intersects = (a, b) => a & b
const union = (a, b) => a | b
// if a subset contains another one, discard it
// e.g [1,2,4] should be discarded if [1,2] is present
const cleanSubsets = bins => bins.filter(big => bins.every(b => big === b || !isIn(b, big)))
function bestClique (decs) {
const cliques = []
forall(decs, (next, el) => {
if (intersects(next.s, el)) { return { skip: true } }
const s = union(next.s, el)
cliques.push({ s, v: next.v.concat(el) })
return { s }
})
return cliques.sort((a, b) => b.v.length - a.v.length)[0]
}
// in case we have duplicated numbers in the list,
// they are still uniq thanks to their id: i (idem position in the list)
const buildNumbers = v => v.map((n, i) => {
const u = new Number(n)
u.i = i
return u
})
function run (v) {
const numbers = buildNumbers(v)
const subs = buildSubsets(numbers)
const bins = subs.map(s => decs2bin(s.v.map(n => n.i)))
const clique = bestClique(cleanSubsets(bins))
const indexedSubs = clique.v.map(bin2decs)
const subsets = indexedSubs.map(sub => sub.map(i => numbers[i].valueOf()))
console.log('subsets', JSON.stringify(subsets))
}
run([1, -1, 2, -2])
run([-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18, 10, -10])
run([-5, -4, 5, 2, 3, -1])
这个问题是 NP 完全问题，因为它是两个 NP 完全问题的组合：
- 找到总和为
0 的单个子集称为 subset sum problem
- 当你找到总和为
0的所有子集时，你必须解决一个具有特殊条件的exact cover problem：你想要最大化子集的数量。
以下步骤将提供解决方案：
- 使用动态规划求和为
0('https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution) 的子集
- 为了最大化子集的数量，可以使用 D. Knuth's Algorithm X 来找到确切的覆盖。
几点说明：
首先，我们知道存在精确覆盖，因为数字列表的总和为0。
其次，我们只能使用不是任何其他子集超集的子集。因为，如果 A 是 X 的超集（两者之和为 0），则 A 不能位于子集数最多的封面中。令A, B, C, ... 为最大子集数的覆盖，那么我们可以用X和[=代替A 33=]（很容易看出 A\X 个元素的总和是 0），我们得到封面 X、A\X、B、C, ...这样更好。
第三，当我们使用算法X时，搜索树中的所有路径都会成功。设 A、B、C、... 是由非重叠子集组成的路径，每个子集的总和为 0。那么complent也有0的和（可能是另一个子集的超集，然后我们就用2.）。
如您所见，这里没有新内容，我将只使用众所周知的 techniques/algorithms。
找到总和为 0 的子集。
算法众所周知。这是基于 Wikipedia explanations
的 Python 实现
class Q:
def __init__(self, values):
self.len = len(values)
self.min = sum(e for e in values if e <= 0)
self.max = sum(e for e in values if e >= 0)
self._arr = [False] * self.len * (self.max - self.min + 1)
def __getitem__(self, item):
index, v = item
return self._arr[v * self.len + index]
def __setitem__(self, item, value):
index, v = item
self._arr[v * self.len + index] = value
class SubsetSum:
def __init__(self, values):
self._values = values
self._q = Q(values)
def prepare(self):
for s in range(self._q.min, self._q.max + 1):
self._q[0, s] = (self._values[0] == s)
for i in range(self._q.len):
self._q[i, 0] = True
for i in range(1, self._q.len):
v = self._values[i]
for s in range(self._q.min, self._q.max + 1):
self._q[i, s] = (v == s) or self._q[i - 1, s] or self._q[
i - 1, s - v]
def subsets(self, target=0):
yield from self._subsets(self._q.len - 1, target, [])
def _subsets(self, i, target, p):
assert i >= 0
v = self._values[i]
c = self._q[i - 1, target]
b = self._q[i - 1, target - v]
if i == 0:
if target == 0:
if p:
yield p
elif self._q[0, target]:
yield p + [i]
else:
if self._q.min <= target - v <= self._q.max and self._q[
i - 1, target - v]:
yield from self._subsets(i - 1, target - v, p + [i])
if self._q[i - 1, target]:
yield from self._subsets(i - 1, target, p)
工作原理如下：
arr = [-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]
arr = sorted(arr)
s = SubsetSum(arr)
s.prepare()
subsets0 = list(s.subsets())
print(subsets0)
输出：
[[13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [13, 12, 11, 10, 9, 7, 6, 5, 3, 2, 1, 0], [13, 12, 11, 10, 9, 4, 2, 1, 0], [13, 12, 11, 10, 8, 7, 4, 2, 1, 0], [13, 12, 11, 10, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 10, 7, 2, 1, 0], [13, 12, 11, 10, 6, 5, 3, 1, 0], [13, 12, 11, 9, 8, 7, 4, 2, 1, 0], [13, 12, 11, 9, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 9, 7, 2, 1, 0], [13, 12, 11, 9, 6, 5, 3, 1, 0], [13, 12, 11, 8, 7, 6, 5, 3, 1, 0], [13, 12, 11, 8, 4, 1, 0], [13, 12, 11, 1, 0], [13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 1, 0], [13, 12, 10, 9, 8, 2, 1, 0], [13, 12, 10, 9, 7, 6, 5, 3, 1, 0], [13, 12, 10, 9, 4, 1, 0], [13, 12, 10, 8, 7, 4, 1, 0], [13, 12, 10, 7, 1, 0], [13, 12, 9, 8, 7, 4, 1, 0], [13, 12, 9, 7, 1, 0], [13, 11, 10, 8, 6, 5, 4, 3, 2, 0], [13, 11, 10, 6, 5, 3, 2, 0], [13, 11, 9, 8, 6, 5, 4, 3, 2, 0], [13, 11, 9, 6, 5, 3, 2, 0], [13, 11, 8, 7, 6, 5, 3, 2, 0], [13, 11, 8, 4, 2, 0], [13, 11, 7, 6, 5, 4, 3, 2, 1], [13, 11, 7, 6, 5, 4, 3, 0], [13, 11, 2, 0], [13, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0], [13, 10, 9, 7, 6, 5, 3, 2, 0], [13, 10, 9, 4, 2, 0], [13, 10, 8, 7, 4, 2, 0], [13, 10, 8, 6, 5, 4, 3, 2, 1], [13, 10, 8, 6, 5, 4, 3, 0], [13, 10, 7, 2, 0], [13, 10, 6, 5, 3, 2, 1], [13, 10, 6, 5, 3, 0], [13, 9, 8, 7, 4, 2, 0], [13, 9, 8, 6, 5, 4, 3, 2, 1], [13, 9, 8, 6, 5, 4, 3, 0], [13, 9, 7, 2, 0], [13, 9, 6, 5, 3, 2, 1], [13, 9, 6, 5, 3, 0], [13, 8, 7, 6, 5, 3, 2, 1], [13, 8, 7, 6, 5, 3, 0], [13, 8, 4, 2, 1], [13, 8, 4, 0], [13, 7, 6, 5, 4, 3, 1], [13, 2, 1], [13, 0], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 0], [12, 11, 10, 9, 8, 2, 0], [12, 11, 10, 9, 7, 6, 5, 3, 2, 1], [12, 11, 10, 9, 7, 6, 5, 3, 0], [12, 11, 10, 9, 4, 2, 1], [12, 11, 10, 9, 4, 0], [12, 11, 10, 8, 7, 4, 2, 1], [12, 11, 10, 8, 7, 4, 0], [12, 11, 10, 8, 6, 5, 4, 3, 1], [12, 11, 10, 7, 2, 1], [12, 11, 10, 7, 0], [12, 11, 10, 6, 5, 3, 1], [12, 11, 9, 8, 7, 4, 2, 1], [12, 11, 9, 8, 7, 4, 0], [12, 11, 9, 8, 6, 5, 4, 3, 1], [12, 11, 9, 7, 2, 1], [12, 11, 9, 7, 0], [12, 11, 9, 6, 5, 3, 1], [12, 11, 8, 7, 6, 5, 3, 1], [12, 11, 8, 4, 1], [12, 11, 1], [12, 10, 9, 8, 7, 6, 5, 4, 3, 1], [12, 10, 9, 8, 2, 1], [12, 10, 9, 8, 0], [12, 10, 9, 7, 6, 5, 3, 1], [12, 10, 9, 4, 1], [12, 10, 8, 7, 4, 1], [12, 10, 7, 1], [12, 9, 8, 7, 4, 1], [12, 9, 7, 1], [11, 10, 8, 6, 5, 4, 3, 2], [11, 10, 6, 5, 3, 2], [11, 9, 8, 6, 5, 4, 3, 2], [11, 9, 6, 5, 3, 2], [11, 8, 7, 6, 5, 3, 2], [11, 8, 4, 2], [11, 7, 6, 5, 4, 3], [11, 2], [10, 9, 8, 7, 6, 5, 4, 3, 2], [10, 9, 7, 6, 5, 3, 2], [10, 9, 4, 2], [10, 8, 7, 4, 2], [10, 8, 6, 5, 4, 3], [10, 7, 2], [10, 6, 5, 3], [9, 8, 7, 4, 2], [9, 8, 6, 5, 4, 3], [9, 7, 2], [9, 6, 5, 3], [8, 7, 6, 5, 3], [8, 4]]
减少子集的数量
我们有 105 个子集，总和为 0，但我们可以删除作为其他子集超集的子集。我们需要一个函数来查找一个元素列表是否包含另一个列表中的所有元素。在 Python:
import collections
def contains(l1, l2):
"""
Does l1 contain all elements of l2?
"""
c = collections.Counter(l1)
for e in l2:
c[e] -= 1
return all(n >= 0 for n in c.values())
现在，我们可以删除作为另一个子集超集的子集。
def remove_supersets(subsets):
subsets = sorted(subsets, key=len)
new_subsets = []
for i, s1 in enumerate(subsets):
for s2 in subsets[:i]: # smaller subsets
if contains(s1, s2):
break
else: # not a superset
new_subsets.append(s1)
return new_subsets
我们的情况：
subsets0 = remove_supersets(subsets0)
print(len(subsets0))
输出：
[[13, 0], [11, 2], [8, 4], [13, 2, 1], [12, 11, 1], [10, 7, 2], [9, 7, 2], [12, 10, 7, 1], [12, 9, 7, 1], [10, 9, 4, 2], [10, 6, 5, 3], [9, 6, 5, 3], [12, 11, 10, 7, 0], [12, 11, 9, 7, 0], [12, 10, 9, 8, 0], [12, 10, 9, 4, 1], [8, 7, 6, 5, 3], [12, 11, 10, 9, 4, 0], [12, 10, 9, 8, 2, 1], [11, 7, 6, 5, 4, 3], [13, 7, 6, 5, 4, 3, 1]]
[[0, 2, 10, 6, 4], [0, 2, 10, 8, 1], [0, 2, 11, 5, 4], [0, 2, 11, 7, 1], [0, 16, 9, 4], [0, 16, 15, 1], [0, 18, 19], [3, 2, 12, 11], [3, 2, 13, 10], [3, 17, 16], [3, 19, 14], [20, 14, 1]]
我们设法将子集的数量减少到 21 个，这是一个很好的改进，因为我们需要探索所有可能性来找到精确的覆盖。
算法 X
我在这里不使用跳舞链接（我认为该技术是为 C 等低级语言设计的，但如果需要，您可以在 Python 中实现它们）。我们只需要跟踪剩余的子集：
class Matrix:
def __init__(self, subsets, ignore_indices=set()):
self._subsets = subsets
self._ignore_indices = ignore_indices
def subset_values(self, i):
assert i not in self._ignore_indices
return self._subsets[i]
def value_subsets_indices(self, j):
return [i for i, s in self._subsets_generator() if j in s]
def _subsets_generator(self):
return ((i, s) for i, s in enumerate(self._subsets) if
i not in self._ignore_indices)
def rarest_value(self):
c = collections.Counter(
j for _, s in self._subsets_generator() for j in s)
return c.most_common()[-1][0]
def take_subset(self, i):
s = self._subsets[i]
to_ignore = {i2 for i2, s2 in self._subsets_generator() if
set(s2) & set(s)}
return Matrix(self._subsets,
self._ignore_indices | to_ignore)
def __bool__(self):
return bool(list(self._subsets_generator()))
最后是 cover 函数：
def cover(m, t=[]):
if m: # m is not empty
j = m.rarest_value()
for i in m.value_subsets_indices(j):
m2 = m.take_subset(i)
yield from cover(m2, t + [i])
else:
yield t
最后，我们有：
m = Matrix(subsets0)
ts = list(cover(m))
t = max(ts, key=len)
print([[arr[j] for j in subsets0[i]] for i in t])
输出：
[[100, -100], [10, -10], [15, 2, 1, -18], [15, 5, -20], [60, 20, -80]]
我正在尝试解决这个问题，但我不知道如何解决。
假设我有一个正数和负数的列表，其和保证为 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，即使使用蛮力方法我如何设法解决它？我只需要一个小数字列表的解决方案。
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]))
基本上，此解决方案会收集原始列表中总和为零的所有子集，然后尝试将尽可能多的子集合并在一起而不会发生冲突。它在最坏情况下为 运行s O(2^{2N}) 时间，其中 N 是列表的长度，但它应该达到大约 O(2^N) 的平均情况，因为通常应该总和为 0 的子集太多了。
编辑：我添加了部分以便于解释算法
第 1 部分：我遍历原始列表的所有可能的 2^N-1 个非空子集，并检查这些子集中哪些子集的和为 0；任何可行的零和子集都被添加到列表 cand（表示为 [1,2^N-1] 范围内的整数，并在构成子集的索引处设置位）。
第 2 部分：dp 是一个动态规划 table 存储总和为 0 的子集的最大数量，这些子集可以使用整数 i 表示的子集在 dp[i]。最初，dp 的所有条目都设置为 0，除了 dp[0] = 1，因为空集的总和为 0。然后我从 0 到 2^N-1 遍历每个子集，并且我 运行遍历候选子集列表并尝试合并两个子集。
第3节：这只是回溯寻找答案：在填写dp时，我还保留了一个数组back，用于存储最近添加的子集以实现子集[=13] =] 在 back[i]。所以我找到了最大化子集数的子集，总和为 0 ind = dp.index(max(dp))，然后我从那里回溯，通过删除最近添加的子集来缩小子集，直到我最终回到空集。
下面和Michael Huang基本一样的思路，多了30行...
有小集团的解决方案
我们可以预构建所有总和为0的子集
- 构建 1 个元素的子集；
- 然后通过重复使用之前的大小 2
- 并保留那些总和为零的人
现在说这样的子集是图的一个节点。 然后一个节点与另一个节点相关，前提是它们的关联子集没有共同的数字。
因此我们要构建图的最大团：
- 在一个集团中，所有节点都具有相同的关系，它们的子集是不相交的
- 最大团给了我们最大数量的子集
function forall (v, reduce) {
const nexts = v.map((el, i) => ({ v: [el], i, s: el })).reverse()
while (nexts.length) {
const next = nexts.pop()
for (let i = next.i + 1; i < v.length; ++i) {
const { s, skip } = reduce(next, v[i])
if (!skip) {
nexts.push({ v: next.v.concat(v[i]), s: s, i })
}
}
}
}
function buildSubsets (numbers) {
const sums = []
forall(numbers, (next, el) => {
const s = next.s + el
if (s === 0) {
sums.push({ s, v: next.v.concat(el) })
return { s, skip: true }
}
return { s }
})
return sums
}
const bin2decs = bin => {
const v = []
const s = bin.toString(2)
for (let i = 0; i < s.length; ++i) {
if (intersects(dec2bin(i), bin)) {
v.push(i)
}
}
return v
}
const dec2bin = dec => Math.pow(2, dec)
const decs2bin = decs => decs.reduce((bin, dec) => union(dec2bin(dec), bin), 0)
// Set methods on int
const isIn = (a, b) => (a & b) === a
const intersects = (a, b) => a & b
const union = (a, b) => a | b
// if a subset contains another one, discard it
// e.g [1,2,4] should be discarded if [1,2] is present
const cleanSubsets = bins => bins.filter(big => bins.every(b => big === b || !isIn(b, big)))
function bestClique (decs) {
const cliques = []
forall(decs, (next, el) => {
if (intersects(next.s, el)) { return { skip: true } }
const s = union(next.s, el)
cliques.push({ s, v: next.v.concat(el) })
return { s }
})
return cliques.sort((a, b) => b.v.length - a.v.length)[0]
}
// in case we have duplicated numbers in the list,
// they are still uniq thanks to their id: i (idem position in the list)
const buildNumbers = v => v.map((n, i) => {
const u = new Number(n)
u.i = i
return u
})
function run (v) {
const numbers = buildNumbers(v)
const subs = buildSubsets(numbers)
const bins = subs.map(s => decs2bin(s.v.map(n => n.i)))
const clique = bestClique(cleanSubsets(bins))
const indexedSubs = clique.v.map(bin2decs)
const subsets = indexedSubs.map(sub => sub.map(i => numbers[i].valueOf()))
console.log('subsets', JSON.stringify(subsets))
}
run([1, -1, 2, -2])
run([-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18, 10, -10])
run([-5, -4, 5, 2, 3, -1])
这个问题是 NP 完全问题，因为它是两个 NP 完全问题的组合：
- 找到总和为
0的单个子集称为 subset sum problem - 当你找到总和为
0的所有子集时，你必须解决一个具有特殊条件的exact cover problem：你想要最大化子集的数量。
以下步骤将提供解决方案：
- 使用动态规划求和为
0('https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution) 的子集
- 为了最大化子集的数量，可以使用 D. Knuth's Algorithm X 来找到确切的覆盖。
几点说明：
首先，我们知道存在精确覆盖，因为数字列表的总和为0。
其次，我们只能使用不是任何其他子集超集的子集。因为，如果
A是X的超集（两者之和为0），则A不能位于子集数最多的封面中。令A,B,C, ... 为最大子集数的覆盖，那么我们可以用X和[=代替A33=]（很容易看出A\X个元素的总和是0），我们得到封面X、A\X、B、C, ...这样更好。第三，当我们使用算法X时，搜索树中的所有路径都会成功。设
A、B、C、... 是由非重叠子集组成的路径，每个子集的总和为0。那么complent也有0的和（可能是另一个子集的超集，然后我们就用2.）。
如您所见，这里没有新内容，我将只使用众所周知的 techniques/algorithms。
找到总和为 0 的子集。
算法众所周知。这是基于 Wikipedia explanations
的 Python 实现class Q:
def __init__(self, values):
self.len = len(values)
self.min = sum(e for e in values if e <= 0)
self.max = sum(e for e in values if e >= 0)
self._arr = [False] * self.len * (self.max - self.min + 1)
def __getitem__(self, item):
index, v = item
return self._arr[v * self.len + index]
def __setitem__(self, item, value):
index, v = item
self._arr[v * self.len + index] = value
class SubsetSum:
def __init__(self, values):
self._values = values
self._q = Q(values)
def prepare(self):
for s in range(self._q.min, self._q.max + 1):
self._q[0, s] = (self._values[0] == s)
for i in range(self._q.len):
self._q[i, 0] = True
for i in range(1, self._q.len):
v = self._values[i]
for s in range(self._q.min, self._q.max + 1):
self._q[i, s] = (v == s) or self._q[i - 1, s] or self._q[
i - 1, s - v]
def subsets(self, target=0):
yield from self._subsets(self._q.len - 1, target, [])
def _subsets(self, i, target, p):
assert i >= 0
v = self._values[i]
c = self._q[i - 1, target]
b = self._q[i - 1, target - v]
if i == 0:
if target == 0:
if p:
yield p
elif self._q[0, target]:
yield p + [i]
else:
if self._q.min <= target - v <= self._q.max and self._q[
i - 1, target - v]:
yield from self._subsets(i - 1, target - v, p + [i])
if self._q[i - 1, target]:
yield from self._subsets(i - 1, target, p)
工作原理如下：
arr = [-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]
arr = sorted(arr)
s = SubsetSum(arr)
s.prepare()
subsets0 = list(s.subsets())
print(subsets0)
输出：
[[13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [13, 12, 11, 10, 9, 7, 6, 5, 3, 2, 1, 0], [13, 12, 11, 10, 9, 4, 2, 1, 0], [13, 12, 11, 10, 8, 7, 4, 2, 1, 0], [13, 12, 11, 10, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 10, 7, 2, 1, 0], [13, 12, 11, 10, 6, 5, 3, 1, 0], [13, 12, 11, 9, 8, 7, 4, 2, 1, 0], [13, 12, 11, 9, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 9, 7, 2, 1, 0], [13, 12, 11, 9, 6, 5, 3, 1, 0], [13, 12, 11, 8, 7, 6, 5, 3, 1, 0], [13, 12, 11, 8, 4, 1, 0], [13, 12, 11, 1, 0], [13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 1, 0], [13, 12, 10, 9, 8, 2, 1, 0], [13, 12, 10, 9, 7, 6, 5, 3, 1, 0], [13, 12, 10, 9, 4, 1, 0], [13, 12, 10, 8, 7, 4, 1, 0], [13, 12, 10, 7, 1, 0], [13, 12, 9, 8, 7, 4, 1, 0], [13, 12, 9, 7, 1, 0], [13, 11, 10, 8, 6, 5, 4, 3, 2, 0], [13, 11, 10, 6, 5, 3, 2, 0], [13, 11, 9, 8, 6, 5, 4, 3, 2, 0], [13, 11, 9, 6, 5, 3, 2, 0], [13, 11, 8, 7, 6, 5, 3, 2, 0], [13, 11, 8, 4, 2, 0], [13, 11, 7, 6, 5, 4, 3, 2, 1], [13, 11, 7, 6, 5, 4, 3, 0], [13, 11, 2, 0], [13, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0], [13, 10, 9, 7, 6, 5, 3, 2, 0], [13, 10, 9, 4, 2, 0], [13, 10, 8, 7, 4, 2, 0], [13, 10, 8, 6, 5, 4, 3, 2, 1], [13, 10, 8, 6, 5, 4, 3, 0], [13, 10, 7, 2, 0], [13, 10, 6, 5, 3, 2, 1], [13, 10, 6, 5, 3, 0], [13, 9, 8, 7, 4, 2, 0], [13, 9, 8, 6, 5, 4, 3, 2, 1], [13, 9, 8, 6, 5, 4, 3, 0], [13, 9, 7, 2, 0], [13, 9, 6, 5, 3, 2, 1], [13, 9, 6, 5, 3, 0], [13, 8, 7, 6, 5, 3, 2, 1], [13, 8, 7, 6, 5, 3, 0], [13, 8, 4, 2, 1], [13, 8, 4, 0], [13, 7, 6, 5, 4, 3, 1], [13, 2, 1], [13, 0], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 0], [12, 11, 10, 9, 8, 2, 0], [12, 11, 10, 9, 7, 6, 5, 3, 2, 1], [12, 11, 10, 9, 7, 6, 5, 3, 0], [12, 11, 10, 9, 4, 2, 1], [12, 11, 10, 9, 4, 0], [12, 11, 10, 8, 7, 4, 2, 1], [12, 11, 10, 8, 7, 4, 0], [12, 11, 10, 8, 6, 5, 4, 3, 1], [12, 11, 10, 7, 2, 1], [12, 11, 10, 7, 0], [12, 11, 10, 6, 5, 3, 1], [12, 11, 9, 8, 7, 4, 2, 1], [12, 11, 9, 8, 7, 4, 0], [12, 11, 9, 8, 6, 5, 4, 3, 1], [12, 11, 9, 7, 2, 1], [12, 11, 9, 7, 0], [12, 11, 9, 6, 5, 3, 1], [12, 11, 8, 7, 6, 5, 3, 1], [12, 11, 8, 4, 1], [12, 11, 1], [12, 10, 9, 8, 7, 6, 5, 4, 3, 1], [12, 10, 9, 8, 2, 1], [12, 10, 9, 8, 0], [12, 10, 9, 7, 6, 5, 3, 1], [12, 10, 9, 4, 1], [12, 10, 8, 7, 4, 1], [12, 10, 7, 1], [12, 9, 8, 7, 4, 1], [12, 9, 7, 1], [11, 10, 8, 6, 5, 4, 3, 2], [11, 10, 6, 5, 3, 2], [11, 9, 8, 6, 5, 4, 3, 2], [11, 9, 6, 5, 3, 2], [11, 8, 7, 6, 5, 3, 2], [11, 8, 4, 2], [11, 7, 6, 5, 4, 3], [11, 2], [10, 9, 8, 7, 6, 5, 4, 3, 2], [10, 9, 7, 6, 5, 3, 2], [10, 9, 4, 2], [10, 8, 7, 4, 2], [10, 8, 6, 5, 4, 3], [10, 7, 2], [10, 6, 5, 3], [9, 8, 7, 4, 2], [9, 8, 6, 5, 4, 3], [9, 7, 2], [9, 6, 5, 3], [8, 7, 6, 5, 3], [8, 4]]
减少子集的数量
我们有 105 个子集，总和为 0，但我们可以删除作为其他子集超集的子集。我们需要一个函数来查找一个元素列表是否包含另一个列表中的所有元素。在 Python:
import collections
def contains(l1, l2):
"""
Does l1 contain all elements of l2?
"""
c = collections.Counter(l1)
for e in l2:
c[e] -= 1
return all(n >= 0 for n in c.values())
现在，我们可以删除作为另一个子集超集的子集。
def remove_supersets(subsets):
subsets = sorted(subsets, key=len)
new_subsets = []
for i, s1 in enumerate(subsets):
for s2 in subsets[:i]: # smaller subsets
if contains(s1, s2):
break
else: # not a superset
new_subsets.append(s1)
return new_subsets
我们的情况：
subsets0 = remove_supersets(subsets0)
print(len(subsets0))
输出：
[[13, 0], [11, 2], [8, 4], [13, 2, 1], [12, 11, 1], [10, 7, 2], [9, 7, 2], [12, 10, 7, 1], [12, 9, 7, 1], [10, 9, 4, 2], [10, 6, 5, 3], [9, 6, 5, 3], [12, 11, 10, 7, 0], [12, 11, 9, 7, 0], [12, 10, 9, 8, 0], [12, 10, 9, 4, 1], [8, 7, 6, 5, 3], [12, 11, 10, 9, 4, 0], [12, 10, 9, 8, 2, 1], [11, 7, 6, 5, 4, 3], [13, 7, 6, 5, 4, 3, 1]]
[[0, 2, 10, 6, 4], [0, 2, 10, 8, 1], [0, 2, 11, 5, 4], [0, 2, 11, 7, 1], [0, 16, 9, 4], [0, 16, 15, 1], [0, 18, 19], [3, 2, 12, 11], [3, 2, 13, 10], [3, 17, 16], [3, 19, 14], [20, 14, 1]]
我们设法将子集的数量减少到 21 个，这是一个很好的改进，因为我们需要探索所有可能性来找到精确的覆盖。
算法 X
我在这里不使用跳舞链接（我认为该技术是为 C 等低级语言设计的，但如果需要，您可以在 Python 中实现它们）。我们只需要跟踪剩余的子集：
class Matrix:
def __init__(self, subsets, ignore_indices=set()):
self._subsets = subsets
self._ignore_indices = ignore_indices
def subset_values(self, i):
assert i not in self._ignore_indices
return self._subsets[i]
def value_subsets_indices(self, j):
return [i for i, s in self._subsets_generator() if j in s]
def _subsets_generator(self):
return ((i, s) for i, s in enumerate(self._subsets) if
i not in self._ignore_indices)
def rarest_value(self):
c = collections.Counter(
j for _, s in self._subsets_generator() for j in s)
return c.most_common()[-1][0]
def take_subset(self, i):
s = self._subsets[i]
to_ignore = {i2 for i2, s2 in self._subsets_generator() if
set(s2) & set(s)}
return Matrix(self._subsets,
self._ignore_indices | to_ignore)
def __bool__(self):
return bool(list(self._subsets_generator()))
最后是 cover 函数：
def cover(m, t=[]):
if m: # m is not empty
j = m.rarest_value()
for i in m.value_subsets_indices(j):
m2 = m.take_subset(i)
yield from cover(m2, t + [i])
else:
yield t
最后，我们有：
m = Matrix(subsets0)
ts = list(cover(m))
t = max(ts, key=len)
print([[arr[j] for j in subsets0[i]] for i in t])
输出：
[[100, -100], [10, -10], [15, 2, 1, -18], [15, 5, -20], [60, 20, -80]]