总和等于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获得。

在这两种算法中，我会选择动态编程，因为它非常简单，并且对于大多数数据集具有良好的运行时间。

但是，如果整数都是非负数，并且与维基百科页面上的描述相符，那么实际上可以使用近似算法在多项式时间内完成此操作。