alle möglichen Summen Erhalten Sie aus einer Liste von Zahlen

Question

Lassen Sie uns sagen, dass ich eine Liste von Zahlen haben: 2, 2, 5, 7

Nun sollte das Ergebnis des Algorithmus alle möglichen Summen enthalten.

In diesem Fall: 2 + 2, 2 + 5, 5 + 7, 2 + 2 + 5, 2 + 2 + 5 + 7, 2 + 5 + 7, 5 + 7

Ich würde mag dies mit der dynamischen Programmierung erreichen. Ich habe versucht, eine Matrix zu verwenden, aber bis jetzt habe ich keinen Weg gefunden, alle Möglichkeiten zu bekommen.

Answer 1

Hend von der Frage, glaube ich, dass die Antwort gepostet von AT-2016 ist richtig, und es gibt keine Lösung, die das Konzept der dynamischen Programmierung ausnutzen können, um die Komplexität zu reduzieren.

Hier ist, wie Sie dynamische Programmierung ausnutzen können, um eine ähnliche Frage zu lösen, die die Summe aller möglichen Unterfolgensummen zurückgibt.

sich das Array {2, 2, 5, 7}: Die verschiedenen möglichen Untersequenzen sind:

{2}, {2}, {5}, {7}, {2,5}, { 2,5}, {5,7}, {2,5,7}, {2,5,7}, {2,2,5,7}, {2,2}, {2,7}, { 2,7}, {2,2,7}, {2,2,5}

Die Frage ist also, die Summe all dieser Elemente aus all diesen Subsequenzen zu finden. Dynamische Programmierung kommt zur Rettung !!

Ordne die Subsequenzen, basierend auf dem Endelement eines jeden Subsequenz:

1. Subsequenzen mit dem ersten Element endet: {2}
2. Subsequenzen mit dem zweiten Element endet: {2}, {2,2 }
3. Untersequenzen, die mit dem dritten Element enden: {5}, {2,5}, {2,5}, {2,2,5}
4. Untersequenzen, die mit dem vierten Element enden: {7}, {5 , 7}, {2,7}, {2,7}, {2,2,7}, {2,5,7}, {2,5,7}, {2,2,5,7}.

Hier ist der Code-Schnipsel:

Das Array 's []' die Summen für 1,2,3,4 individuell berechnet, dh, s [2] berechnet die Summe aller Teilfolgen endet mit drittem Element. Das Array 'dp []' berechnet die Gesamtsumme bis jetzt.

s[0]=array[0]; 
dp[0]=s[0]; 
k = 2; 
for(int i = 1; i < n; i ++) 
{ 
    s[i] = s[i-1] + k*array[i]; 
    dp[i] = dp[i-1] + s[i]; 
    k = k * 2; 
} 
return dp[n-1]; 

Answer 2

Diese in C# und in einem Array durchgeführt wird, um die möglichen Summen zu finden, die ich früher verwendet:

static void Main(string[] args) 
{ 
    //Set up array of integers 
    int[] items = { 2, 2, 5, 7 }; 

    //Figure out how many bitmasks is needed 

    //4 bits have a maximum value of 15, so we need 15 masks. 
    //Calculated as: (2^ItemCount) - 1 
    int len = items.Length; 
    int calcs = (int)Math.Pow(2, len) - 1; 

    //Create array of bitmasks. Each item in the array represents a unique combination from our items array 
    string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, '0')).ToArray(); 

    //Spit out the corresponding calculation for each bitmask 
    foreach (string m in masks) 
    { 
     //Get the items from array that correspond to the on bits in the mask 
     int[] incl = items.Where((c, i) => m[i] == '1').ToArray(); 

     //Write out the mask, calculation and resulting sum 
     Console.WriteLine(
      "[{0}] {1} = {2}", 
      m, 
      String.Join("+", incl.Select(c => c.ToString()).ToArray()), 
      incl.Sum() 
     ); 
    } 

    Console.ReadKey(); 
} 

Mögliche Ausgänge:

[0001] 7 = 7 
[0010] 5 = 5 
[0011] 5 + 7 = 12 
[0100] 2 = 2 

Answer 3

Dies ist keine Antwort auf die Frage, weil es nicht die Anwendung der dynamischen Programmierung demonstriert. Vielmehr stellt es fest, dass dieses Problem Multisets umfasst, für die Einrichtungen in Sympy verfügbar sind.

>>> from sympy.utilities.iterables import multiset_combinations 
>>> numbers = [2,2,5,7] 
>>> sums = [ ] 
>>> for n in range(2,1+len(numbers)): 
...  for item in multiset_combinations([2,2,5,7],n): 
...   item 
...   added = sum(item) 
...   if not added in sums: 
...    sums.append(added) 
...    
[2, 2] 
[2, 5] 
[2, 7] 
[5, 7] 
[2, 2, 5] 
[2, 2, 7] 
[2, 5, 7] 
[2, 2, 5, 7] 
>>> sums.sort() 
>>> sums 
[4, 7, 9, 11, 12, 14, 16]