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

(Версия решения) ваша проблема все еще NP-полная. Идея состоит в том, что если бы мы могли решить вашу проблему, то (например, для каждого размера подмножества) мы могли бы спросить, сколько наборов в сумме меньше V, а сколько в сумме меньше V-1, и разница этих двух чисел будет скажите нам, есть ли подмножества, сумма которых равна V - таким образом, мы могли бы решить проблему суммы подмножеств. [Это не полное доказательство, потому что это редукция Тьюринга, а не много на одно сокращение.]

Однако существует простое решение динамического программирования, которое выполняется за время O (nLV). [Причина, по которой это не доказывает, что P = NP, заключается в том, что V может быть экспоненциальным в размере ввода: с n битами вы можете представлять значения до 2 ⁿ. Но если предположить, что ваш V не является экспоненциальным, это не проблема.]

Пусть num [v] [k] [i] обозначает количество подмножеств размера k первых i элементов S, которые суммируются с v. Вы можете вычислить их как (для каждого i):

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

где S [i] - i-й элемент в вашей последовательности. (Любой набор размера k, который суммируется с v, либо не использует S [i], поэтому он учитывается в num [v] [k] [i-1], либо он использует S [i], что означает, что остальная часть подмножество имеет k-1 элементов, использует только первые числа i-1 в последовательности и суммируется с vS [i].) Наконец, подсчитайте num [v] [L] [| S |] для каждого v меньше V ; это твой ответ.

Кроме того, вы можете опустить третий индекс, если будете делать это осторожно (запускайте цикл вниз для каждого i и т. Д.); Я включил это только для ясности.

Я не готов представить доказательства, но это звучит так, как будто это может быть применимо к схеме динамического программирования: свести в таблицу список подмножеств размера 2, использовать их для компьютерных подмножеств размера 3 и т. Д., Чтобы вам нужно было только изучить небольшая коллекция перспектив.

Одна оптимизация, которая приходит на ум, заключается в следующем: закажите последовательность (если это не так). Выберите первые элементы L-1 с его начала, а затем выберите последний элемент так, чтобы это было максимально возможное значение (следующее по величине значение в последовательности дало бы слишком большую сумму). Отбросьте остальную часть последовательности, потому что эти элементы в любом случае никогда не могут быть частью допустимого подмножества.

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

Решение динамического программирования для задачи суммы подмножества генерирует таблицу, которая содержит этот ответ (то есть логическую таблицу V на N, где V - максимальное количество элементов, а N - максимальное количество элементов, которые могут быть в наборе, который удовлетворяет ограничения; каждое логическое значение истинно, если сумма элементов ‹= N равна‹ = V). Итак, если N * V для вас не слишком велико, существует приемлемо быстрый алгоритм. Решение суммы подмножества - это просто самый высокий элемент набора в этой таблице, для которого число элементов составляет ‹= N / 2.

Если это только положительные целые числа, вы можете выполнить этап проверки при необходимости;

Возьмите сумму L-1 наименьших целых чисел в наборе. Если это сумма X, то n-X должно быть ниже самого большого элемента, если проблема предполагается имеет решение. Если подумать, вы можете устранить другие L таким образом ...

Ну, во-первых, поскольку вы указываете size = L, тогда, даже если вы не можете придумать ничего умного и просто использовать грубую силу, у вас будут (N выберите L) отдельные суммы в худшем случае, так что это немного лучше чем n ^^ L (ну, L + 1, так как вы затем суммируете каждое подмножество).

Это звучит как n выберите категорию проблемы. Создание k-подмножеств n описано в Руководстве по разработке алгоритмов Скиены, и книга предлагает перечислить соответствующие подмножества в лексикографическом порядке (например, рекурсивно). Затем проведите суммирование и сравнение каждого подмножества.

Если у вас есть отсортированный набор, вы, вероятно, можете исключить невозможные решения из области решений.

Возможно, формулировка динамического программирования является частью PTAS FPTAS.