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

Question

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

Answer 1

Ваша проблема - это вариация проблемы Subset Sum и является NP-полной.

Чтобы понять почему, давайте предположим, что у вас есть алгоритм, который может решить вашу проблему, и он дает ответ с суммой s. Затем вы доказали, что не существует подмножества целых чисел, равного s - 1, т. Е. У вас есть решение проблемы суммы подмножеств.

Если производительность не является проблемой, вы можете просто перечислить все возможные наборы. Если производительность является проблемой, вы можете попробовать поискать на странице Википедии идеи о том, как оптимизировать этот вид алгоритма, например, с помощью динамического программирования. Алгоритм на этой странице должен фактически решить вашу проблему почти так же эффективно, как и проблема суммы подмножеств.

Answer 2

У меня была такая же проблема! Если все N целых чисел положительны и ограничены константой C, то существует решение с требованиями времени и пространства O (NC).

Пизингер обнаружил алгоритм динамического программирования с линейным временем, чтобы найти максимальное значение под порогом, которое похоже на обратную задачу. Таким образом, если вы вычтите желаемый порог из общей суммы целых чисел, вы можете использовать этот новый порог с алгоритмом Пизингера, чтобы найти все числа НЕ в нужном наборе.

В зависимости от размера целых чисел, это может быть или не быть возможным.

Бумага Писингера: http://www.diku.dk/~pisinger/95-6.ps

Код: Быстрое решение алгоритма подмножества суммы по Пизингеру

Answer 3

«наименьшая сумма»: есть классическая проблема «максимальной суммы», хорошо описанная здесь: http://wordaligned.org/articles/the-maximum-subsequence-problem

Это всего лишь крошечный вариант с условием «превышает порог» - просто дополнительный оператор IF в вашем цикле.