我有 2 个集合，集合 A 包含一组随机数，集合 B 的元素是集合 A 的子集的总和。

例如，

A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96]

B = [183, 36, 231, 128, 137]

我想用这样的数据找出哪个数字是哪个子集的总和。

S = [[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]]

我能够用 python 编写非常愚蠢的暴力破解代码。

class SolvedException(BaseException):
    pass

def solve(sums, nums, answer):
    num = nums[-1]

    for i in range(0, len(sums)):
        sumi = sums[i]
        if sumi == 0:
            continue
        elif sumi - num < 0:
            continue
        answer[i].append(num)

        sums[i] = sumi - num

        if len(nums) != 1:
            solve(sums, nums[:-1], answer)
        elif sumi - num == 0:
            raise SolvedException(answer)

        sums[i] = sumi

        answer[i].pop()

try:
    solve(B, A, [list() for i in range(0, len(B))])
except SolvedException as e:
    print e.args[0]

此代码适用于小数据，但计算我的数据(有 71 个数字和 10 个总和)需要数十亿年。

我可以使用一些更好的算法或优化。

对不起，我的英语不好，代码效率低下。

编辑:抱歉，我意识到我没有准确描述问题。

由于 A 中的每个元素都用于构成 B 的元素，sum(A) == sum(B)

此外，集合S必须集合A的分区。

最佳答案

这被称为子集和问题，它是一个众所周知的 NP 完全问题。所以基本上没有有效的解决方案。参见示例 https://en.wikipedia.org/wiki/Subset_sum_problem

不过如果你的数N不是太大，还有一个伪多项式算法，使用动态规划: 您从左到右阅读列表 A 并保留可行且小于 N 的总和的列表。如果您知道对于给定 A 可行的数字，您可以轻松获得对于 A + [a 可行的数字].因此动态规划。对于您在此处给出的大小的问题，它通常足够快。

这是一个 Python 快速解决方案:

def subsetsum(A, N):
    res = {0 : []}
    for i in A:
        newres = dict(res)
        for v, l in res.items():
            if v+i < N:
                newres[v+i] = l+[i]
            elif v+i == N:
                return l+[i]
        res = newres
    return None

然后

>>> A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96]
>>> subsetsum(A, 183)
[15, 15, 33, 36, 39, 45]

OP 编辑​​后:

现在我正确地理解了你的问题，我仍然认为你的问题可以有效地解决，只要你有一个有效的子集求和求解器:我会在 B 上使用分而治之的解决方案:

• 将B切成大致相等的两 block B1和B2
• 使用子集求和求解器在 A 中搜索其和等于 sum(B1) 的所有子集 S。
• 对于每个这样的S:
  • 递归调用 solve(S, B1) 和 solve(A - S, B2)
  • 如果两者都成功了，你就有了解决方案

但是，您下面的 (71, 10) 问题对于我建议的动态规划解决方案来说是无法解决的。

顺便说一句，这里是您的问题的快速解决方案不是使用分而治之，但它包含我的动态求解器的正确适应以获得所有解决方案:

class NotFound(BaseException):
    pass

from collections import defaultdict
def subset_all_sums(A, N):
    res = defaultdict(set, {0 : {()}})
    for nn, i in enumerate(A):
        # perform a deep copy of res
        newres = defaultdict(set)
        for v, l in res.items():
            newres[v] |= set(l)
            for v, l in res.items():
                if v+i <= N:
                    for s in l:
                        newres[v+i].add(s+(i,))
                        res = newres
                        return res[N]

def list_difference(l1, l2):
    ## Similar to merge.
    res = []
    i1 = 0; i2 = 0
    while i1 < len(l1) and i2 < len(l2):
        if l1[i1] == l2[i2]:
            i1 += 1
            i2 += 1
        elif l1[i1] < l2[i2]:
            res.append(l1[i1])
            i1 += 1
        else:
            raise NotFound
            while i1 < len(l1):
                res.append(l1[i1])
                i1 += 1
                return res

def solve(A, B):
    assert sum(A) == sum(B)
    if not B:
        return [[]]
        res = []
        ss = subset_all_sums(A, B[0])
        for s in ss:
            rem = list_difference(A, s)
            for sol in solve(rem, B[1:]):
                res.append([s]+sol)
                return res

然后:

>>> solve(A, B)
[[(15, 33, 39, 96), (36,), (8, 15, 60, 68, 80), (9, 46, 73), (45, 92)],
 [(15, 33, 39, 96), (36,), (8, 9, 15, 46, 73, 80), (60, 68), (45, 92)],
 [(8, 15, 15, 33, 39, 73), (36,), (9, 46, 80, 96), (60, 68), (45, 92)],
 [(15, 15, 73, 80), (36,), (8, 9, 33, 39, 46, 96), (60, 68), (45, 92)],
 [(15, 15, 73, 80), (36,), (9, 39, 45, 46, 92), (60, 68), (8, 33, 96)],
 [(8, 33, 46, 96), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (45, 92)],
 [(8, 33, 46, 96), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (45, 92)],
 [(9, 15, 33, 46, 80), (36,), (8, 15, 39, 73, 96), (60, 68), (45, 92)],
 [(45, 46, 92), (36,), (8, 15, 39, 73, 96), (60, 68), (9, 15, 33, 80)],
 [(45, 46, 92), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (9, 60, 68)],
 [(45, 46, 92), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (8, 33, 96)],
 [(45, 46, 92), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (8, 33, 96)],
 [(9, 46, 60, 68), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (45, 92)]]

>>> %timeit solve(A, B)
100 loops, best of 3: 10.5 ms per loop

所以对于这种规模的问题来说它是相当快的，尽管这里没有优化。

关于python - 多子集和计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42422921/