LINUX.ORG.RU
Форум — Development  

Поиск подмножества с заданной суммой


0

0

Надо из элементов заданного списка выбрать ЛЮБОЕ подмножество, сумма элементов которого даст заданную сумму (не факт, что такое подмножество есть). Да, практически тот самый рюкзак :)

Тупой перебор долго работает. Элементов >> 10.

Где поискать оптимизированные алгоритмы?

★★★★★

Это называется "Subset Sum Problem," NP-полная. 
Вот тут объясняется один алгоритм: www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html

grob ★★★★★
()
Ответ на: комментарий от grob

Спасибо. Пошел по азимуту...

yyk ★★★★★
() автор топика
Ответ на: комментарий от yyk

Сам мудак! (это я себе)

Загнав в рекурсию с сохранением промежуточных вариантов в хэш-таблице получил то, что надо.

yyk ★★★★★
() автор топика
Ответ на: комментарий от yyk

че-то не пойму: нету опасности, что во время рекурсии, NP-полная функция съест весь стэк? (или все-таке размер задачи не такой уж и большой?)

phrm ★★
()
Ответ на: комментарий от phrm

Скорее всего задача не слишком большая: размер списка ~200 элементов.

Да и рекурсия бывает разная.

yyk ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development