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

Question

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

Учитывая значение V, размер набора L и последовательность чисел [1, N] S, сколько подмножеств размера L в S суммируют до V?

Это отличается от задачи о сумме подмножеств тремя способами:

1. Мне важно, сколько подмножеств меньше , чем данное значение, а не сколько равно .
2. Размеры подмножества фиксированы.
3. Меня волнует , сколько устанавливает сумму меньше V, а не только существует ли она.

Есть ли достаточно эффективный алгоритм для решения этой проблемы?

Edit: Очевидно, что это можно сделать в O (N выбирают L), используя алгоритм генерации комбинации. Что меня действительно интересует, так это умные хаки, чтобы значительно ускорить его.

Answer 1

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

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

Пусть num [v] [k] [i] обозначает количество подмножеств size-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 и т. Д.); Я включил его только для ясности.

Answer 2

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

Answer 3

Если это только натуральные числа, вы можете выполнить шаг проверки , если вам нужно ;

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

Answer 4

Динамическое программирование для решения проблемы суммы подмножеств создает таблицу, содержащую этот ответ (т. Е. Булеву таблицу V на N, где V - максимальное количество элементов, а N - максимальное количество элементов, которые могут быть в наборе это удовлетворяет ограничениям, причем каждый логический тип равен true, если <= N элементов суммируют с <= V). Поэтому, если N * V не слишком велико для вас, существует приемлемо быстрый алгоритм. Решение подмножества сумм - это просто элемент с наибольшим набором в этой таблице, для которого количество элементов составляет <= N / 2. </p>

Answer 5

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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