Нужен алгоритм поиска оптимального набора слагаемых (по дереву) Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Древовидный Переключить на: Стандартный Переключить на: Линейный

[neosapient]

Здравствуйте.
Мне нужен алгоритм, который оптимально быстро найдет слагаемые для получению нужной суммы, либо определит, что данную сумму нельзя получить.

Есть массив целых положительных и отрицательных чисел. Нуля быть не может. Сами числа могут повторяться...
Например, +1,+1,+1,+7,-4,1000,-996, -3.
Найти сочетание слагаемых, чтобы в сумме получить 3.

1) Минимальное условие задачи - найти ХОТЯ БЫ ОДНО сочетание слагаемых, чтобы получить нужную сумму.
2) Оптимально будет, если будут найден вариант(ы) с минимальным числом слагаемых.

==============================================================
Сейчас пошел в упор - делаю поиск в глубину, с полным перебором вариантов.
Но этот подход плох тем хотя бы по тому, что решения может не быть, а я об этом узнаю, только перебрав все сочетания.
Число вариантов возможных комбинаций слагаемых можно рассчитать по формуле (2^n)-1
Таким образом,
* для 1 слагаемого - только 1 сочетание
* для 2 слагаемых - 3 сочетания
* для 3 слагаемых - 7 сочетаний
* для 4 слагаемых - 15 сочетаний
* для 5 слагаемых - 31 сочетание
.........
* для 26 слагаемых - 67108863 сочетания

Пример того какие сочетания могут быть. Допустим у меня массив слагаемых из пяти элементов: a, b, c, d, e. Тогда я составляю следующие варианты.
a, b, c, d, e,
ab, ac, ad, ae, bc, bd, be, cd, ce, de
abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde
abcd, abce, abde, acde, bcde
abcde
Итого для пяти слагаемых 31 вариант суммы.

Если для 26 элементов, программа слишком долго рассчитывает, то как быть, когда у меня будет 100 элементов?
Подскажите оптимальный алгоритм