crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> Нужен алгоритм поиска оптимального набора слагаемых (по дереву)
neosapient
  опции профиля:
сообщение 10.9.2009, 13:01
Сообщение #1


Новичок


Группа: Новичок
Сообщений: 6
Регистрация: 27.6.2008
Пользователь №: 216

Спасибо сказали: 0 раз(а)




Репутация:   0  


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

Есть массив целых положительных и отрицательных чисел. Нуля быть не может. Сами числа могут повторяться...
Например, +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
  опции профиля:
сообщение 10.9.2009, 13:39
Сообщение #2


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


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

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

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

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

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

Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 29.3.2024, 11:44