鉴于我有 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!)。如果不存在多项式时间算法,请解释原因。