Здравствуйте.
Мне нужен алгоритм, который оптимально быстро найдет слагаемые для получению нужной суммы, либо определит, что данную сумму нельзя получить.
Есть массив целых положительных и отрицательных чисел. Нуля быть не может. Сами числа могут повторяться...
Например, +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 элементов?
Подскажите оптимальный алгоритм
так вот с ходу не вникая
могу предложить отсортировать по возростанию массив. потм найти максимально возможное число если все положительные сложить и минимальное возможное если все отрицательные сложить.
в начале поиска получая необходимую сумму сравниваем она должна попасть прежде всего в диапазон между максимумом и минимумом, иначе поиск не начинаем.(думаю это откинет довольно много вариантов)
далее ищем допустим бинарно самое близкое к сумме число затем ищем остаток опять же бинарно, в случае если не нашли берем второе самое близкое к сумме число и бинарно ищем остаток.
если не подходят 2 слагаемых, ищем 3 и так далее.
а вообще я как раз решил заняться такого рода алгоритмами.
вот есть литературка, могу на мыло скинуть.
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)