@Demond98

Как реализовать алгорим задачи о сумме подмножеств?

Дано множество вещественных чисел N. Задача заключается в нахождении (одного достаточно) подмножества N, чтобы сумма чисел этого подмножества равнялась S. Числа могут быть отрицательными, а также повторяться.
Пробовал решить перебором, но количество чисел достаточно большое(330 штук) и в этом столетии мне не успеть посчитать. Видел решения с помощью динамического программирования, но они либо не поддерживают отрицательные числа, либо не поддерживают повторяющиеся числа. Что делать - не знаю

p.s Числа в множестве N могут повторяться. пример N = {1, 1 , 2, 5}
  • Вопрос задан
  • 1737 просмотров
Пригласить эксперта
Ответы на вопрос 4
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Необязательно же искать оптимальный (кратчайший) набор, дающий нужную сумму?

Предлагаю от простого к сложному двигаться:
  1. проверить каждое из N на остаток деления S % n = 0 Вдруг, найдётся число, которое надо просто повторить m раз, чтобы получить S
  2. проверить каждую пару чисел из N на разницу: если найдётся разница в 1, можно получить любое число через эти два
  3. проверить каждую тройку чисел из N Подзадача та же, получить 1. Есть 1 – есть любое целое.
Ответ написан
Adamos
@Adamos
Отрицательные числа, конечно, здорово портят задачу ;) классические переборные алгоритмы такой подлянки не имеют.
Но общую логику имеет смысл сохранить: ваша цель - определенная сумма, можно к ней стремиться. На каждом шаге подбора варианты сортируются по тому, насколько их прибавление приближает вас к искомой сумме (по модулю). И перебор до тех пор, пока первое же число не дает разность 0.
Ответ написан
mindtester
@mindtester
https://youtu.be/UtO6HIp1908?list=RDUtO6HIp1908
у гугла спросить не судьба? Задача о сумме подмножеств

ps кстати, сведения о вычислительной сложности идут первым же пунктом
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Обычная динамическое программирование работает для повторяющихся чисел, тут не должно быть проблем. Отрицательные числа решаются просто - считаете все возможные суммы только положительных чисел стандартной динамикой и отдельно только для отрицательных чисел (опустив знак). Потом одним циклом перебираете сумму положительных чисел x>=S и смотрите, если x-S можно набрать отрицательными числами. На общую сложность этот цикл не влияет.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы