什麼是確定某些數字的所有可能總和的最有效算法

Question

我們有一組數字A = {X1，X2，...，Xn}以及什麼是最有效的算法來確定所有可能的總和A集的元素？它可以是幾個具有相似效率的算法。我寧願不要他們使用非常複雜的圖書館，也不要那種數學。

我更喜歡僞代碼，Java或C++的解決方案

PS。當我說高效時，我的意思是當然算法的共同效率，而不是執行算法的風格。

Answer 1

在設計算法之前需要考慮一些問題。我將首先對集合中元素的範圍和集合的大小做一些假設。

首先可以說，數字是A = {X1，X2，X3 ... XN}，他們是在範圍民< =曦< =最大。通過這個前提，最大可能總和將爲SUM = X1 + X2 + C3 + ... + Xn。

在這種情況下，我會從大小爲SUM + 1的數組possibleSums開始。數組表示是否可以分別使用0或1。所以如果讓我們從給定集合中說14是可能的，那麼possibleSums [14]將有值1，而如果讓我們說87作爲任何子集的總和是不可能的，那麼possibleSums [87]將是0.因爲0總是可以通過選擇一個空子集，所以我會開始初始化possibleSums [0] = 1。

之後，我通過每個元件僖陣列的並且對於每個possibleSums [I] == 1，我將設置possibleSums迭代[I +Ⅺ] = 1。這是很清楚的，因爲如果讓我們說從先前的元素中可以得到13，那麼通過添加下一個元素3,15也是可能的。

下面是在C++中的代碼：

// Sum = X1 + X2 + X3 + ... Xn 

bool possibleSums[ Sum + 1 ]; 

void findAllPossibleSums(int X[ N ]) 
{ 
    // Because in an empty subset sum is 0 
    possibleSums[ 0 ] = true; 

    for(int i = 0; i < N; i++) 
    { 
    /* Now minimum start sum when X[ i ] is included will be X[ i ] and of course maximum sum will be SUM 
    */ 
    for(int j = SUM; j >= X[ i ]; j--) 
    { 
     // If sum = j - X[ i ] is possible then sum j is also possible 
     if(possibleSums[ j - X[ i ] ]) 
     { 
     possibleSums[ j ] = true; 
     } 
    } 
    } 
    for(int i = 0; i < SUM; i++) 
    { 
    // Print the possible sums or whatever you want 
    if(possibleSums[ i ]) 
     cout << i <<"\n"; 
    } 
} 

的在最壞的情況下在上述算法的複雜度是：

O（最大值* N * N）時刻

O（最大* n）在太空

但空間複雜性可以減少使用（Max * n）位來存儲possibleSums而不是數組。

允許分析對於某些情況複雜（假設possibleSums使用位實現）：

對於最大值= 100和n = 10^6，它是達到10^10計算爲時間，這是巨大的。

解決這個問題的另一種方法是強力的，我稱之爲索引i和裏面的遞歸方法，因爲有兩種可能性（添加一個數字或離開它），我曾經添加和稱爲遞歸，然後第二次調用遞歸而不添加它。這在時間上具有O（2^n）的複雜性。

問題實際上是着名的Subset Sum Problem的變體，它存在於一類NP-complete問題中。請參考維基鏈接來參考一些可以通過僞多項式時間算法解決的特殊情況。上述情況或其他特殊情況可能適用於您的使用。