Toplam ile eşitlik toplamı serileri eşittir X

Question

Tam sayı koleksiyonum var. Değerlerin toplamının X.

'a eşit olması için tüm olasılıklara ihtiyacım var this gibi bir şeye ihtiyacım var.

O yazılabilir: vb.net

bir subset sum problem var

Answer 1

, Delphi, C#, php, KO, piton, cobol, vb. Ve bu .

Bunu gerçekleştirmenin tek yolu tüm olası kombinasyonları oluşturmak ve toplam değerleri karşılaştırmak olacaktır. Optimizasyon teknikleri de var.

Burada C# biri:

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 kesin çözüm için en iyi çalışma zamanını doğuracak. Wikipedia'daki The Subset Sum Problem page, algoritma için bazı sözde kod içeriyor. Esas olarak, tüm sayıları sipariş edersiniz ve olası tüm sıraları toplayarak ekleme sayısını en aza indirirsiniz. Çalışma zamanı yalancı polinomdur.

Bir polinom algoritması için Approximation Algorithm kullanabilirsiniz. Sözde kod Subset Sum Problem page da kullanılabilir.

İki algoritmadan biri, doğrudan doğruya ve çoğu veri kümesine sahip iyi bir çalışma süresine sahip olduğu için dinamik programlamayı seçerdim.

Tamsayıların tümü negatif değilse ve Wikipedia sayfasındaki açıklamaya uyuyorsa, bunu aslında yaklaşık algoritma ile polinom zamanında yapabilirsiniz.