Псевдополиномиальное разделение чисел по времени

В информатике псевдополиномиальное разделение чисел по времени представляет собой алгоритм псевдополиномиального времени для решения проблемы разделения .

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

Предположим, что входными данными для алгоритма является мультимножество $S$ мощности $N$:

S знак равно { Икс ₁ , ..., Икс _N }

Пусть K — сумма всех элементов S. в То есть: K = x ₁ + ... + x _N . Мы построим алгоритм, который определит, существует ли подмножество S , сумма которого равна $\lfloor K/2\rfloor$. Если есть подмножество, то:

если K четное, остальная часть S также равна $\lfloor K/2\rfloor$

если K нечетно, то остальная часть S в сумме равна $\lceil K/2\rceil$. Это максимально хорошее решение.

например1 S = {1, 2, 3, 5}, K = sum(S) = 11, K/2 = 5, Найдите подмножество из S , ближайшее к K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1

например2 S = {1, 3, 7}, K = sum(S) = 11, K/2 = 5, Найдите подмножество из S , ближайшее к K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3

Рекуррентное отношение

Мы хотим определить, существует ли подмножество S , сумма которого равна $\lfloor K/2\rfloor$. Позволять:

p ( i , j ) будет True, если подмножество { x ₁ , ..., x _j } суммируется с i , и False в противном случае.

Тогда р ( $\lfloor K/2\rfloor$, N ) истинно тогда и только тогда, когда существует подмножество S , сумма которого равна $\lfloor K/2\rfloor$. Целью нашего алгоритма будет вычисление p ( $\lfloor K/2\rfloor$, Н ). В помощь этому у нас есть следующее рекуррентное соотношение :

p ( i , j ) истинно, если либо p ( i , j − 1) истинно, либо если p ( i − x _j , j − 1) истинно

p ( i , j ) является ложным в противном случае

Обоснование этого следующее: существует некоторое подмножество S , сумма которого равна i, используя числа

х ₁ , ..., х _j

тогда и только тогда, когда верно одно из следующих утверждений:

Существует подмножество { x ₁ , ..., x _{j −1} }, сумма которого равна i ;

существует подмножество { x ₁ , ..., x _{j −1} }, сумма которого равна i − x _j , поскольку x _j + сумма этого подмножества = i .

Псевдополиномиальный алгоритм

Алгоритм заключается в построении таблицы размеров $\lfloor K/2\rfloor$ к $N$ содержащий значения повторения. Помните, что $K$ это сумма всех $N$ элементы в $S$. Как только вся таблица будет заполнена, мы возвращаемся $P(\lfloor K/2\rfloor ,N)$. Ниже представлено изображение таблицы $P$. Существует синяя стрелка от одного блока к другому, если значение целевого блока может зависеть от значения исходного блока. Эта зависимость является свойством рекуррентного отношения.

Зависимости записи таблицы ( i , j )

function can_be_partitioned_equally(S) is
    input: A list of integers S.
    output: True if S can be partitioned into two subsets that have equal sum.

    n ← |S|
    K ← sum(S)
    P ← empty boolean table of size ($\lfloor K/2\rfloor$ + 1) by (n + 1)

    initialize top row (P(0,x)) of P to True
    initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False

    for i from 1 to $\lfloor K/2\rfloor$
        for j from 1 to n
            x = S[j-1]
            if (i-x) >= 0 then
                P(i, j) ← P(i, j-1) or P(i-x, j-1)
            else
                P(i, j) ← P(i, j-1)

   return P($\lfloor K/2\rfloor$, n)

Пример

Ниже приведена таблица P для использованного выше примера S = {3, 1, 1, 2, 2, 1}:

Результат примера выполнения алгоритма на таблице P

Анализ

Этот алгоритм работает за время O ( K/2 N ) , где N — количество элементов во входном наборе, а K — сумма элементов во входном наборе.

Алгоритм можно распространить на k задачу многоразбиения -way, но тогда требуется O ( n ( k − 1) m ^{к - 1} ) памяти, где m — наибольшее число во входных данных, что делает его непрактичным даже для k = 3, если только входные данные не являются очень маленькими числами.

Этот алгоритм можно обобщить для решения проблемы суммы подмножеств .