Легче ли решить этот вариант задачи о подмножестве сумм?
У меня есть проблема, связанная с проблемой подмножества сумм, и мне интересно, облегчают ли различия, то есть разрешимые в разумные сроки.
При заданном значении V, заданном размере L и последовательности чисел [1,N] S, сколько подмножеств L размера в S суммируют с меньшим, чем V?
Это отличается от проблемы суммы подмножеств тремя способами:
- Меня волнует, сколько подмножеств меньше заданного значения, а не сколько равно.
- Размеры подмножества являются фиксированными.
- Меня волнует, сколько наборов сумма меньше, чем V, а не только существуют ли какие-либо.
Есть ли достаточно эффективный алгоритм для решения этой проблемы?
Изменить: Очевидно, это можно сделать в O(N выбрать L) с использованием алгоритма генерации комбинации. Что меня действительно интересует, так это умные взломы, чтобы значительно ускорить его.
9 ответов
(Версия решения) ваша проблема все еще NP-завершена. Идея состоит в том, что если бы мы могли решить вашу проблему, то (скажем, для каждого размера подмножества) мы могли бы спросить, сколько наборов сумма меньше V, а сколько сумма меньше V-1, и разница между этими двумя числами скажите нам, есть ли подмножества, которые суммируют ровно V - таким образом, мы могли бы решить проблему суммы подмножеств. [Это не полное доказательство, потому что это сокращение Тьюринга, а не одно сокращение.]
Однако существует простое решение для динамического программирования, которое выполняется за время O(nLV). [Причина, по которой это не доказывает, что P=NP, состоит в том, что V может быть экспоненциальным по входному размеру: с n битами вы можете представлять значения до 2n. Но если предположить, что ваш 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 и т. Д.); Я включил это только для ясности.
Я не готов представить доказательство, но это звучит так, как будто оно поддается динамической схеме программирования: табулируйте список подмножеств размера 2, используйте их для компьютерных подмножеств размера 3 и т. Д., Так что вам нужно только изучить небольшая коллекция перспектив.
Если это только положительные целые числа, вы можете сделать шаг проверки, если вам нужно;
Возьмите сумму самых маленьких целых чисел L-1 в наборе. Если это сумма X, то nX должно быть ниже наибольшего элемента, если предполагается, что проблема имеет решение. Если подумать, вы можете устранить другие L таким образом...
Разве это не просто проблема с рюкзаком? Может быть, я ошибаюсь, хотя.
Динамическое программирование для решения проблемы суммы подмножеств создает таблицу, которая содержит этот ответ (то есть булева таблица V на N, где V - максимальное количество элементов, а N - максимальное количество элементов, которые могут быть в наборе, который удовлетворяет ограничения: каждый логический тип имеет значение true, если сумма элементов <=N равна <=V). Поэтому, если N * V не слишком велико для вас, существует приемлемо быстрый алгоритм. Решение суммы подмножеств - это просто элемент с наибольшим набором в этой таблице, для которого количество элементов составляет <= N/2.
Одна из оптимизаций, которая приходит на ум, заключается в следующем: упорядочить вашу последовательность (если это не так). Выберите первые элементы L-1 с самого начала, а затем выберите последний элемент так, чтобы это было наибольшее возможное значение (следующее наибольшее значение в последовательности даст слишком большую сумму). Откажитесь от остальной части последовательности, потому что эти элементы никогда не могут быть частью действительного подмножества в любом случае.
После этого я думаю, что это полный поиск снова. Но с другой стороны, возможны и другие варианты оптимизации.
Ну, во-первых, поскольку вы указываете размер =L, то даже если вы не можете придумать ничего умного и просто использовать грубую силу, у вас будет (N выбрать L) отдельные суммы в худшем случае, так что это немного лучше чем n^^L (ну, L+1, так как вы бы суммировали каждое подмножество).
Это звучит как n выбрать категорию k. Генерация k-подмножеств n описана в Руководстве по разработке алгоритмов Skiena, и в книге предлагается перечислить соответствующие подмножества в лексикографическом порядке (например, рекурсивно). Затем сделайте свою сумму и сравнение по каждому подмножеству.
Если у вас есть отсортированный набор, вы, вероятно, могли бы удалить невозможные решения из пространства решений.
Возможно, формулировка динамического программирования схожа с PTAS FPTAS.