Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Нужен алгоритм поиска оптимального набора слагаемых (по дереву)
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
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 элементов?
Подскажите оптимальный алгоритм
kwisp
так вот с ходу не вникая
могу предложить отсортировать по возростанию массив. потм найти максимально возможное число если все положительные сложить и минимальное возможное если все отрицательные сложить.

в начале поиска получая необходимую сумму сравниваем она должна попасть прежде всего в диапазон между максимумом и минимумом, иначе поиск не начинаем.(думаю это откинет довольно много вариантов)
далее ищем допустим бинарно самое близкое к сумме число затем ищем остаток опять же бинарно, в случае если не нашли берем второе самое близкое к сумме число и бинарно ищем остаток.
если не подходят 2 слагаемых, ищем 3 и так далее.

а вообще я как раз решил заняться такого рода алгоритмами.
вот есть литературка, могу на мыло скинуть.
Цитата
Сортировка
-- Поразрядная
-- Быстрая
-- Пирамидальная
-- Слиянием
-- Пузырьком + модификации
-- Вставками
-- Шелла
-- Выбором
-- FAQ
-- Топологическая
-- Быстрая с составными ключами

Структуры данных
-- Введение в абстрактные структуры
-- АВЛ-деревья
-- Красно-черные деревья
-- Деревья со случайным поиском
-- Слоёные списки (скип-списки)
-- Хеш-таблицы
-- Б, Б+ и Б++ деревья
-- Обходы бинарных деревьев
-- Hashed Array Trees[Перевод]
-- StringBTree
-- Triangle Mesh

Поиск. Строки и последовательности
-- Точный подстроки в строке
-- Нечеткий поиск
-- Проверка на подпоследовательность
-- Общие подпоследовательности. Дистанция
-- Поиск hcs, lis, his
-- Максимальная повторяющаяся подстрока
-- Общие элементы двух массивов
-- Бинарный поиск
-- Интерполяционный поиск
-- Бинарный поиск с определением ближайших узлов
-- Частный случай lis
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2022 IPS, Inc.