题
考虑到我有米非空不同组(标记为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的首选!)。如果没有多项式时间算法存在,请说明原因。
解决方案
这是很容易看出,(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
我个人认为圭多作出关于MUL一个可怕的决定。
其他提示
>>> 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
不隶属于 StackOverflow