總和等於X的數組值總和等於X

Question

我有一個整數集合。我需要得到所有可能值的總和值等於X.

我需要類似this。

它可以寫成：德爾福，C＃，PHP，回報率，蟒蛇，COBOL，VB，vb.net

Answer 1

這是一個subset sum problem。它是NP-Complete。

實現此目的的唯一方法是生成所有可能的組合並比較總和值。儘管存在優化技術。

下面是一個在C＃：

static class Program 
{ 
    static int TargetSum = 10; 
    static int[] InputData = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 

    static void Main() 
    { 
     // find all permutations 
     var permutations = Permute(InputData); 

     // check each permutation for the sum 
     foreach (var item in permutations) { 

      if (item.Sum() == TargetSum) { 

       Console.Write(string.Join(" + ", item.Select(n => n.ToString()).ToArray())); 
       Console.Write(" = " + TargetSum.ToString()); 
       Console.WriteLine(); 

      } 
     } 

     Console.ReadKey(); 
    } 

    static IEnumerable<int[]> Permute(int[] data) { return Permute(data, 0); } 

    static IEnumerable<int[]> Permute(int[] data, int level) 
    { 
     // reached the edge yet? backtrack one step if so. 
     if (level >= data.Length) yield break; 

     // yield the first #level elements 
     yield return data.Take(level + 1).ToArray(); 

     // permute the remaining elements 
     for (int i = level + 1; i < data.Length; i++) { 
      var temp = data[level]; 
      data[level] = data[i]; 
      data[i] = temp; 

      foreach (var item in Permute(data, level + 1)) 
       yield return item; 

      temp = data[i]; 
      data[i] = data[level]; 
      data[level] = temp; 
     } 

    } 
} 

Answer 2

Dynamic Programming將產生最佳運行一個確切的解決方案。維基百科上的The Subset Sum Problem page對算法有一些僞代碼。從本質上講，您可以對所有數字進行排序，並將所有可能的順序相加，以便最大限度地減少添加次數。運行時間是僞多項式。

對於多項式算法，您可以使用Approximation Algorithm。僞碼也可從Subset Sum Problem page獲得。

在這兩種算法中，我會選擇動態編程，因爲它非常簡單，並且對於大多數數據集具有良好的運行時間。

但是，如果整數都是非負數，並且與維基百科頁面上的描述相符，那麼實際上可以使用近似算法在多項式時間內完成此操作。