Существует несколько способов решения этой проблемы. Одним из них является классическое решение DP, которое опубликовали другие. Я собираюсь опубликовать решение, которое использует только O (S) память, где S - это сумма всех целых чисел в массиве (может быть изменено, чтобы обозначить и желаемую сумму), а другое - очень эффективный рандомизированный алгоритм, который может Быть проверенным, чтобы быть очень быстрым даже для сотен тысяч чисел любого размера, и даже рациональных и отрицательных чисел.
Решение DP во времени O (nS) и памяти O (S):
//let F[i] = 1 if we can get sum i and 0 otherwise
F[0] = 1; // we can always make sum 0
for ( int i = 1; i <= n; ++i )
for ( int j = S; j >= numbers[i]; --j )
F[j] |= F[j - numbers[i]]; // basically, if F[j - numbers[i]] == 1, then we
// can add numbers[i] to make F[j] 1, otherwise
// we can't. A bitwise or operation will save us
// an if/else structure basically.
Псевдокод для рандомизированного алгоритма:
Пусть Используется = список чисел, которые вы суммируете.
Пусть Unused = список чисел, которые вы НЕ суммируете.
Пусть tmpsum = 0.
Пусть S = желаемая сумма, которую вы хотите достичь.
for ( each number x you read )
toss a coin:
if it's heads and tmpsum < S
add x to Used
else
add x to Unused
while ( tmpsum != S )
if tmpsum < S
MOVE one random number from Unused to Used
else
MOVE one random number from Used to Unused
print the Used list, containing the numbers you need to add to get S
Это будет намного быстрее, чем решение для динамического программирования, особенно для случайных входов. Единственные проблемы состоят в том, что вы не можете надежно определить, когда решения не существует (вы можете позволить алгоритму работать в течение нескольких секунд, а если он не завершится, предположить, что решения не существует) и что вы не можете быть уверены, что получите решение с минимальным количеством выбранных элементов. Опять же, вы можете добавить некоторую логику, чтобы заставить алгоритм продолжать работу и пытаться найти решение с меньшим количеством элементов, пока не будут выполнены определенные условия остановки, но это сделает его медленнее. Однако, если вас интересует только решение, которое работает, и у вас МНОГО чисел, а желаемая сумма может быть ОЧЕНЬ большой, это, вероятно, лучше, чем алгоритм DP.
Еще одним преимуществом этого подхода является то, что он также будет работать для отрицательных и рациональных чисел без изменений, что неверно для решения DP, поскольку решение DP предполагает использование частичных сумм в качестве индексов массивов, а индексы могут быть только естественными номера. Конечно, вы можете, например, использовать хеш-таблицы, но это сделает решение DP еще медленнее.
Чтобы сгенерировать все комбинации, вы должны поискать обратное отслеживание: http://en.wikipedia.org/wiki/Backtracking
Для этой проблемы вам нужно использовать что-то вроде этого:
void back(int k)
{
if ( k > numElements )
{
// add all the nums[i] for which st[i] == 1 and check
// if their sum is what you desire, then return;
}
for ( int i = 0; i <= 1; ++i )
{
st[k] = i;
back(k + 1);
}
}
Вы должны запустить его на бумаге для небольшого количества элементов, чтобы увидеть, как это работает. Вы можете оптимизировать его, вычисляя сумму по ходу, тем самым избегая окончательного суммирования. Это общая идея.