Блог

У меня простая алгоритмическая проблема.

• У меня есть набор положительных целых чисел S и положительное максимальное целое число i .
• Допустим, сумма S (или подмножество S ) является суммой его элементов.
• Мне нужно найти подмножество s из S , сумма которого не превышает i и является «максимально суммирующей», что означает, что никакое другое подмножество S не имеет большей суммы, чем s без превышения i .

Тривиальное решение, которое я придумал, состоит в том, чтобы просмотреть каждый набор степенного набора S и суммировать целые числа, отслеживая набор с искомыми свойствами, но этот алгоритм, очевидно, экспоненциальный.

Должно быть хорошо известное название для этой проблемы, поскольку я не думаю, что я первый, кто столкнулся с этой необходимостью. Может ли кто-нибудь мне помочь?

Решите задачу о сумме подмножеств для вашего набора, используя динамическое программирование.

Затем сканируйте заполненную таблицу от i-й записи до меньших значений, пока не найдете ненулевую запись (т. Е. Такая сумма существует). Это наибольшая сумма подмножеств, которая не превышает заданного значения.