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

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


0

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

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

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

★★★★★
← сколько значащих цифр обеспечивает long double на i386/i387
C++ → 
Это называется "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 ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← сколько значащих цифр обеспечивает long double на i386/i387
Development
C++ →