0

鉴于我有 m 个非空的不同集合(标记为 Z[1]、Z[2]、...、Z[m]),我的目标是计算所有可能子集的总和,其中每个子集只有一个元素放。每个子集的大小被定义为其成员的乘积。例如:

Z[ 1 ] = {1,2,3}

Z[ 2 ] = {4,5}

Z[ 3 ] = {7,8}

应该导致:

1*4*7 + 1*4*8 + 1*5*7 + 1*5*8 + 2*4*7 + 2*4*8 + 2*5*7 + 2*5*8 + 3*4*7 + 3*4*8 + 3*5*7 + 3*5*8 = 810

虽然这很容易编码(用任何语言),但这是对著名的子集和问题的重述吗?如果没有,请提供计算此总和的多项式时间算法(首选伪代码或 python!)。如果不存在多项式时间算法,请解释原因。

4

2 回答 2

4

很容易看出 (1 + 2 + 3) * (4 + 5) * (7 + 8) = 810。

>>> from operator import mul
>>> from functools import reduce
>>> z = [{1,2,3}, {4,5}, {7,8}]
>>> s = reduce(mul, (sum(zz) for zz in z))
>>> s
810

像 sum() 这样的 Python 函数是什么,但用于乘法?产品()?

我个人认为 Guido 对 mul 做出了一个糟糕的决定。

于 2010-01-19T23:25:27.900 回答
0
>>> z1 = [1, 2, 3]
>>> z2 = [4, 5]
>>> z3 = [7, 8]
>>> s = 0
>>> for a in z1:
        for b in z2:
            for c in z3:
                s += a*b*c      
>>> s
810
于 2010-01-19T23:27:56.177 回答