0

给定一个数组，假设数组 = [ 1,2,3]

我想找出每组 powerset 中的所有产品值。

例如，

功率组是

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

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

如何使用动态编程来实现这一点。

笔记：

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

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);
    }
}

这种技术工作得很好，但是对于小数组，（数组大小 < 32）

4

1 回答 1

0

假设您的输入集是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集合的第一个元素获得哪些产品？

于 2013-08-06T17:08:50.580 回答