c - 每组幂集的值的乘积

给定一个数组，可以说array = [1,2,3]

我想找出每个Powerset集合中的所有产品值。

例如，

功率设定为

{null}
{1} - 1
{2} - 2
{3} - 3
{1,2}- 2
{2,3}- 6
{1,3}- 3
{1,2,3}- 6

表示法：集合后跟集合中值的乘积

如何使用动态编程实现这一目标。

注意：

我尝试过这种方式，找到了

void printPowerSet(int *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {

     int product=1;
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
           product *= counter;
       }
      printf("%d", product);
    }
}

该技术绝对可以正常工作，但是对于小型数组（数组大小

最佳答案

假设您的输入集是S并且具有size元素。这样的事情会起作用：

make an empty set A
for every element s in S {
    make an empty set B
    for every t in A {
        add s*t to B
    }
    A = union of A and B
}

那么，一次使用的总内存最坏的情况是两个集合的大小之和，因此O(number of distinct products))。您的“子问题”将是“使用集合的第一个x元素可以得到什么产品？

关于c - 每组幂集的值的乘积，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18085784/