產品在每一組冪

給定一個數組的值，可以說陣列= [1,2,3]產品在每一組冪

我想找出每組其冪的所有產品的價值。

例如，

的發電機組是

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

這項技術發現冪作品精絕，但對於小數組，（數組大小< 32）

來源

2013-08-06 user650521

我懷疑DP（buttom-up）會改善答案，DP的想法通常是建立所有可能性然後，在這裏，可能性的範圍是'[1，x1 * x2 * ... * xn]' - 這比'2^n'要糟得多，假設所有的除了一個值）'x_i> = 2'。 – amit

@amit：呃，他不需要那樣做，你不會去使用那個範圍內的所有東西，有一種方法可以做到這一點，產品（好吧，'O（不同產品的數量）'） –

@ DennisMeng我們如何才能在O（不同產品的數量）中實現這一點 – user650521

假設你輸入設置爲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-06 17:08:50

產品在每一組冪

回答

相關問題