@Lite_stream

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

Всем привет

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

P.S.; в Java NavigableSet есть метод floor(), который, казалось бы, решает данную задачу, но, например, для представленного выше набора чисел туда бы пришлось записать суммы всех возможных сочетаний без повторений, что привело бы к комбинаторному взрыву.
  • Вопрос задан
  • 78 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Смотрите решение задачи о рюкзаке через динамическое программирование.

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

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

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

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