數組「和和/或從」到「x」嗎？

我想寫的算法（在C）TRUE或FALSE（1或0），這取決於是否在輸入給定的陣列A可以「總和和/或子」來x（見它返回以下澄清）。請注意，A的所有值都是隨機（均勻）採樣的[1，x-1]之間的整數。

澄清和實施例

所謂「總和和/或子」，我的意思是把「+」和「 - 」，在陣列的每個元件的前面和求和。我們稱之爲。

int SumSub (int* A,int x) 
{ 
... 
} 

SumSub({2,7,5},10)

應該返回TRUE爲7-2 + 5 = 10。您會注意到A的第一個元素也可以被視爲負數，因此A中元素的順序無關緊要。

SumSub({2,7,5,2},10)

應該返回FALSE因爲沒有方法來「總和和/或子」的array元素達到x值。請注意，這意味着必須使用A的所有元素。

複雜

設n是A長度。如果必須探索所有可能的組合和減號，則問題的複雜性爲O（2^n）。然而，一些組合比其他組合更有可能，因此值得首先探討（希望輸出將是TRUE）。通常，要求減去最大數量的所有元素的組合是不可能的（因爲A的所有元素均低於x）。另外，如果n>x，嘗試添加A的所有元素是沒有意義的。

問題

我應該如何去寫這個功能呢？

來源

2016-09-14 Remi.b

聽起來像一個典型的揹包問題。數組的元素和大小是否有限制？ – sashas

我想用我的資源可以處理的大小（CPU時間）大小的數組。「A」的元素在[1，x-1]之間有界，其中'x'可以是任何無符號整數。 –

應該*數組中的所有*值用於* sum和/或sub *操作嗎？ – trincot

原問題的解決方案的確如您所說的指數級。但是對於A []中的數字，給定範圍[1，x-1]，則可以生成解多項式。有一個非常簡單的動態編程解決方案。

隨着順序：

時間複雜度：爲O（n^2 * X）

存儲器複雜度：爲O（n^2 * X）元素

其中n = NUM在A []

您需要使用動態規劃方法對這個

你知道，可以在區間[-n X配置的最小，最大範圍內，正 x]。創建大小爲（n）X（2 * n * x + 1）的二維數組。讓我們稱之爲此DP [] []

DP [i] [j] =服用A的所有元素[]從[0..i-1]是否其能夠使值j

所以

DP [10] [3] = 1級是指採取A的前10種元素[]我們可以創建值3

DP [10] [3] = 0表示服用的A []我們前10種元素無法創建值3

這裏是一種僞代碼：

int SumSub (int* A,int x) 
{ 
    bool dp[][];//set all values of this array 0 
    dp[0][0] = true; 
    for(i=1;i<=n;i++) { 
     int val = A[i-1]; 
     for(j=-n*x;j<=n*x;j++) { 
      dp[i][j]=dp[ i-1 ][ j + val ] | dp[ i-1 ][ j - val ]; 
     } 
    } 
    return dp[n][x]; 
}

來源

2016-09-14 17:46:29

不幸的是，您的問題可以減少到subset-sum problem這是NP完成。因此指數型解決方案無法避免。

來源

2016-09-14 15:25:35 sashas

答案始終爲NO的問題也可以「減少爲NP-Complete的子集和問題」。（只輸出'{2,3}，4'）。因此，這種減少的存在並不表現出Remi.b的問題。用於投資者的人們： –

不幸的是，即使x被限制爲0，這也是NP完全的，所以不要期望多項式時間算法。爲了說明這一點，我將簡單地從NP-hard Partition Problem中減少，它詢問給定的多個正整數是否可以劃分爲兩個具有相等和的部分：

假設我們有一個分區問題n個正整數B_1，...，B_n。從中創建一個問題的實例，其中A_i = B_i，每個1 < = i < = n，並設置x = 0。

顯然，如果有B的成兩個部分C和d具有等於和的分區，那麼也有您的問題的實例中的溶液：將一個+在用C的每個數字的前面，並且在- D中每個數字的前面（或其他方向）。由於C和D有相同的總和，所以這個表達式必須等於0.如果我們剛剛創建的問題的實例的解決方案是YES（TRUE），那麼我們可以很容易地創建一個B分區爲兩個部分具有相同的總和：只要將所有正項置於一部分（比如C）和所有負項（當然沒有前面的-）放在另一部分（比如D）中。由於我們知道表達式的總值爲0，它必須是C中（正）數的總和等於D中數的總和（取反）。

因此，對於問題實例對其他問題實例意味着「是」，這意味着對任一問題實例的「否」意味着對另一個問題實例的「否」 - 即兩個問題實例具有相同的解決方案。因此，如果可以在多項式時間內解決問題，那麼也可以在多項式時間內解決NP硬分區問題，方法是構建上述問題實例，使用多時間算法解決問題，並報告它給出的結果。

來源

2016-09-14 15:26:50

數組「和和/或從」到「x」嗎？

回答

相關問題