Есть ли уже существующая структура данных для данной задачи?

Question

[floppa322]

Всем привет

Есть положительные числа (немного, в среднем от 1 до 50-70). Нужно уметь получать набор чисел из имеющегося множества, сумма которых не превосходит какое-то число N, причём наибольшая из таких сумм. Например, для числа N = 1200 и следующего множества {800, 100, 1000, 190 , 150, 1180}, вызвав 3 раза нужный метод, мы бы получили {1000, 190}, {1180}, {800, 100, 150}.

P.S.; в Java NavigableSet есть метод floor(), который, казалось бы, решает данную задачу, но, например, для представленного выше набора чисел туда бы пришлось записать суммы всех возможных сочетаний без повторений, что привело бы к комбинаторному взрыву.

Comments

[Сергей Соколов]

«задача об упаковке» В общем-то решается полным перебором вариантов NP-полная.
bin packing

[floppa322]

Сергей Соколов, спасибо )

Answer 1

[Wataru]

Смотрите решение задачи о рюкзаке через динамическое программирование.

Постройте двумерный массив, который будет говорить, можно ли собрать данную сумму первыми k объектами.

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

Comments

[floppa322]

Благодарю за детальное объяснение