Сумма-подмножество с фиксированным размером подмножества

Question

Задача сумма-подмножество гласит:

Имеет ли набор целых чисел непустое подмножество с нулевой суммой?

Эта проблема является NP-полной в целом.Мне любопытно, если сложность этого небольшого варианта известна:

Учитывая набор целых чисел, есть ли подмножество размера k, чья сумма равна нулю?

Например, если k = 1, вы можете выполнить двоичный поиск, чтобы найти ответ в O(log n).Если k = 2, то вы можете уменьшить его до O(n log n) (например, см. Найти пару элементов из массива, сумма которого равна данному числу ).Если k = 3, то вы можете сделать O(n^2) (например, см. Поиск трех элементов в массиве, сумма которых ближе всего к данному числу ).

Isесть известная граница, которая может быть поставлена ​​для этой проблемы как функция k?

В качестве мотивации я размышлял над этим вопросом Как разделить массив на2 части так, что две части имеют одинаковое среднее значение? и пытается определить, является ли он на самом деле NP-завершенным.Ответ заключается в том, существует ли формула, как описано выше.

За исключением общего решения, мне было бы очень интересно узнать оптимальную оценку для k=4.

Answer 1

Для k = 4, сложность пространства O (n), сложность времени O (n ² * log (n))

Сортировка массива.Начиная с 2 самых маленьких и 2 самых больших элементов, вычислите все lesser суммы 2 элементов (a[i] + a[j]) в неубывающем порядке и все greater суммы 2 элементов (a[k] + a[l]) в не возрастающем порядке.Увеличьте lesser сумму, если общая сумма меньше нуля, уменьшите greater единицу, если общая сумма больше нуля, остановите, если общая сумма равна нулю (успех) или a[i] + a[j] > a[k] + a[l] (сбой).

Хитрость заключается в том, чтобы перебрать все индексы i и j таким образом, чтобы (a[i] + a[j]) никогда не уменьшался.А для k и l, (a[k] + a[l]) никогда не должно увеличиваться.Очередь приоритетов помогает сделать это:

1. Поместить key=(a[i] + a[j]), value=(i = 0, j = 1) в приоритетную очередь.
2. Выскочить (sum, i, j) из приоритетной очереди.
3. Использовать sum ввышеуказанный алгоритм.
4. Поместить (a[i+1] + a[j]), i+1, j и (a[i] + a[j+1]), i, j+1 в приоритетную очередь, только если эти элементы еще не использовались.Чтобы отслеживать используемые элементы, сохраняйте массив максимально используемых «j» для каждого «i».Достаточно использовать только значения для «j», которые больше, чем «i».
5. Продолжить с шага 2.

Для k> 4

Если сложность пространства ограничена O (n), я не могу найти ничего лучше, чем использовать грубую силу для k-4 значений и вышеуказанный алгоритм для оставшихся 4 значений.Временная сложность O (n ^(k-2) * log (n)).

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

Обновление

Если n очень велико (в том же порядке, что и максимальное целочисленное значение), можно реализовать очередь приоритетов O (1), улучшая сложностив O (n ² ) и O (n ^(k-2) ).

Если n >= k * INT_MAX, другой алгоритм с O (n) сложностью пространствавозможный.Предварительно рассчитайте набор битов для всех возможных сумм значений k/2.И использовать его для проверки сумм других k/2 значений.Временная сложность O (n ^{(ceil (k / 2))} ).

Answer 2

Проблема определения того, 0 в W + X + Y + Z = {w + x + y + z |w в W, x в X, y в Y, z в Z} в основном то же самое, за исключением отсутствия раздражающих вырожденных случаев (т. е. проблемы взаимно сводимы с минимальными ресурсами).

Эта проблема (и, таким образом, оригинал для k = 4) имеет O (n ^ 2 log n) -время, O (n) -пространственный алгоритм.Алгоритм O (n log n) -времени для k = 2 (чтобы определить, имеет ли 0 в A + B) доступ к A в отсортированном порядке и B в обратном отсортированном порядке.Таким образом, все, что нам нужно, это итератор O (n) -пространства для A = W + X, который можно использовать симметрично для B = Y + Z. Пусть W = {w1, ..., wn} в отсортированном порядке.Для всех x в X вставьте элемент значения ключа (w1 + x, (1, x)) в очередь с приоритетами.Повторно удалите элемент min (wi + x, (i, x)) и вставьте (wi + 1 + x, (i + 1, x)).

Answer 3

Решение для k = 4 в O (n ^ 2log (n))

Шаг 1: Рассчитать попарную сумму и отсортировать список. Есть n (n-1) / 2 суммы. Таким образом, сложность O (n ^ 2log (n)). Сохраняйте личности людей, которые составляют сумму.

Шаг 2: Для каждого элемента в вышеприведенном списке найдите дополнение и убедитесь, что они не разделяют «индивидов». Существует n ^ 2 поисков, каждый со сложностью O (log (n))

РЕДАКТИРОВАТЬ: Пространственная сложность исходного алгоритма O (n ^ 2). Сложность пространства может быть уменьшена до O (1) путем моделирования виртуальной двумерной матрицы (O (n), если вы рассматриваете пространство для хранения отсортированной версии массива).

Сначала о 2D матрице: отсортируйте числа и создайте матрицу X, используя попарные суммы. Теперь матрица такова, что все строки и столбцы отсортированы. Чтобы найти значение в этой матрице, найдите числа на диагонали. Если число находится между X [i, i] и X [i + 1, i + 1], вы можете в основном сократить пространство поиска вдвое до матриц X [i: N, 0: i] и X [0: i , в]. Полученный алгоритм поиска - O (log ^ 2n) (Я НЕ ОЧЕНЬ УВЕРЕН. МОЖЕТ КТО-НИБУДЬ ПРОВЕРИТЬ ЕГО?).

Теперь вместо использования реальной матрицы используйте виртуальную матрицу, в которой X [i, j] вычисляются по мере необходимости, вместо предварительного их вычисления.

Результирующая сложность времени: O ((nlogn) ^ 2).

PS: в следующей ссылке сказано, что сложность поиска в отсортированной двумерной матрице составляет O (n). Если это так (то есть O (log ^ 2n) неверно), то, наконец, сложность O (n ^ 3).

Answer 4

Вопрос, который очень похож:

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

Он все еще NP-завершен.

Если бы это было не так, сумма подмножеств также была бы в P, так как она могла бы быть представлена ​​как F(1) | F(2) | ... F(n), где F - ваша функция Это будет иметь O(O(F(1)) + O(F(2)) + O(F(n))), который по-прежнему будет полиномиальным, что неверно, поскольку мы знаем, что оно NP-завершено.

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

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

Answer 5

Основываясь на ответе awesomo ... если мы можем предположить, что числа отсортированы, мы можем сделать лучше, чем O (n ^ k) для данного k; просто возьмите все O (n ^ (k-1)) подмножеств размера (k-1), затем выполните бинарный поиск того, что осталось для числа, которое при добавлении к первому (k-1) дает цель. Это O (n ^ (k-1) log n). Это означает, что сложность, конечно, меньше, чем это.

На самом деле, если мы знаем, что сложность O (n ^ 2) для k = 3, мы можем сделать еще лучше для k> 3: выбрать все (k-3) -подмножества, из которых есть O ( n ^ (k-3)), а затем решите задачу в O (n ^ 2) на оставшихся элементах. Это O (n ^ (k-1)) для k> = 3.

Однако, может быть, вы можете сделать еще лучше? Я подумаю об этом.

РЕДАКТИРОВАТЬ: Первоначально я собирался добавить многое, предлагая другой взгляд на эту проблему, но я решил опубликовать сокращенную версию. Я призываю других авторов посмотреть, верят ли они в эту идею. Анализ сложный, но он может быть достаточно сумасшедшим, чтобы работать.

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

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

Далее используйте тот факт, что четные целевые суммы могут быть достигнуты только с использованием четного числа нечетных чисел, а нечетные целевые суммы могут быть достигнуты с использованием только нечетного числа нечетных чисел. Создайте соответствующие подмножества нечетных чисел и рекурсивно вызовите алгоритм, используя четные числа, сумма минус сумма исследуемого поднабора нечетных чисел, а k минус размер подмножества нечетных чисел. Когда k = 1, выполните бинарный поиск. Если когда-либо k> n (не уверен, что это может произойти), верните false.

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

РЕДАКТИРОВАТЬ 2: Пример выше, для иллюстрации.

{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20.
Subset {}:
 {2, 2, 6, 20}, k = 3, sum = 20
 = {1, 1, 3, 10}, k = 3, sum = 10
 Subset {}:
  {10}, k = 3, sum = 10
  Failure
 Subset {1, 1}:
  {10}, k = 1, sum = 8
  Failure
 Subset {1, 3}:
  {10}, k = 1, sum = 6
  Failure
Subset {1, 7}:
 {2, 2, 6, 20}, k = 1, sum = 12
 Failure
Subset {7, 7}:
 {2, 2, 6, 20}, k = 1, sum = 6
 Success

Answer 6

Сложность по времени тривиальна O(n^k) (количество k размерных подмножеств из n элементов).

Поскольку k является заданной константой, a (возможно, довольно высокого порядка)верхние полиномиальные оценки сложности как функция n.