python – 多子集和计算

但是如果您的数字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,96]
>>> subsetsum(A,183)
[15,45]

OP编辑后：

现在我正确地理解了你的问题,我仍然认为你的问题可以有效地解决,前提是你有一个有效的子集求解器：我在B上使用分而治之的解决方案：

>将B切成两个近似相等的部分B1和B2
>使用子集求和求解器在A中搜索其总和等于sum(B1)的所有子集S.
>对于每个这样的S：

>调用递归求解(S,B1)并求解(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,96),(36,),(8,80),(9,73),(45,92)],[(15,(60,68),[(8,92),96)],(15,[(9,[(45,80)],68)],92)]]

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

因此,对于这个大小的问题来说这是非常快的,尽管这里的优化注意到了.