0

m 個の空でない個別のセット (Z[ 1 ]、Z[ 2 ]、...、Z[ m ] とラベル付け) がある場合、それぞれの要素が 1 つだけ存在するすべての可能なサブセットの合計を計算することを目指します。設定。各サブセットのサイズは、そのメンバーの積になるように定義されています。例えば：

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 関数ですが、乗算のためのものは何ですか? 製品（）？

個人的には、グイドはムルに関してひどい決断をしたと思います。

于 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 に答える