Получить все возможные суммы из списка чисел

Question

Допустим, у меня есть список номеров: 2, 2, 5, 7

Теперь результат алгоритма должен содержать все возможные суммы.

В этом случае: 2 + 2, 2 + 5, 5 + 7, 2 + 2 + 5, 2 + 2 + 5 + 7, 2 + 5 + 7, 5 + 7

Я бы как добиться этого, используя динамическое программирование. Я попытался использовать матрицу, но до сих пор я не нашел способ получить все возможности.

Answer 1

Основываясь на вопрос, я думаю, что ответ отправленный AT-2016, является правильным, и нет решения, которое может использовать концепцию динамического программирования для уменьшения сложности.

Вот как вы можете использовать динамическое программирование для решения аналогичного вопроса, который просит вернуть сумму всех возможных сумм подпоследовательности.

Рассмотрим массив {2, 2, 5, 7}: Различные возможные подпоследовательности являются:

{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}

Итак, вопрос состоит в том, чтобы найти сумму всех этих элементов из всех этих подпоследовательностей. Динамическое программирование приходит на помощь !!

организовать подпоследовательности на основе заканчивающегося элемента каждой подпоследовательности:

1. подпоследовательности, заканчивающийся с первым элементом: {2}
2. подпоследовательности с окончанием второго элемента: {2}, {2,2 }
3. подпоследовательности, заканчивающиеся на третий элемент: {5}, {2,5}, {2,5}, {2,2,5}
4. подпоследовательности, заканчивающиеся на четвертый элемент: {7}, {5 , 7}, {2,7}, {2,7}, {2,2,7}, {2,5,7}, {2,5,7}, {2,2,5,7}.

Вот фрагмент кода:

Массив «s []» рассчитывает суммы для 1,2,3,4 индивидуально, то есть, с [2] вычисляет сумму всех подпоследовательностей окончание с третьим элементом. Массив 'dp []' вычисляет общую сумму до сих пор.

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

Это делается в C# и в массиве, чтобы найти возможные суммы, которые я использовал ранее:

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(); 
} 

Возможные выходы:

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

Answer 3

Это не ответ на вопрос, потому что он не демонстрирует применение динамического программирования. Скорее он отмечает, что эта проблема включает в себя мультисетекс, для которого объекты доступны в Sympy.

>>> 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]