python – 多子集和计算

概述我有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] 我有2套,集合A包含一组随机数,而集合B的元素是集合A的子集的总和.

例如,

A = [8,9,15,33,36,39,45,46,60,68,73,80,92,96]B = [183,231,128,137]

我想找到哪个数字是哪个子集的总和与这样的数据.

S = [[45,92],[36],[8,96],[60,68],[9,80]]

我能用python编写非常愚蠢的暴力代码.

class SolvedException(BaseException):    passdef 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的元素,因此总和(A)==总和(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,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):    passfrom collections import defaultdictdef 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 resdef 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

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

总结

以上是内存溢出为你收集整理的python – 多子集和计算全部内容，希望文章能够帮你解决python – 多子集和计算所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。