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

Ответ 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]) никогда не должно увеличиваться. Очередь приоритетов помогает сделать это:

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

При k > 4

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

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

Обновление

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

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

Ответ 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) -time, O (n) -пространственный алгоритм. Алгоритм O (n log n) -time для k = 2 (для определения, является ли 0 в + 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)).

Ответ 3

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

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

Он по-прежнему NP-complete.

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

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

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

Ответ 4

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

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

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

EDIT: Сложность пространства исходного алгоритма равна O (n ^ 2). Сложность пространства может быть сведена к O (1) путем моделирования виртуальной 2D-матрицы (O (n), если вы считаете пространство для хранения отсортированной версии массива).

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

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

Сложная временная сложность: O ((nlogn) ^ 2).

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

Ответ 5

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

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

Ответ 6

Чтобы построить на 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.

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

EDIT: я изначально собирался добавить много предложений, которые могут повлечь за собой другую проблему, но я решил опубликовать сокращенную версию. Я призываю другие плакаты посмотреть, считают ли они, что эта идея имеет какие-то достоинства. Анализ сложный, но он может быть просто сумасшедшим, чтобы работать.

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

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

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

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

EDIT2: пример выше, для иллюстрации.

{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