3-РАЗДЕЛНАЯ проблема

Question

вот еще один вопрос динамического программирования ( Vazirani ch6 )

Рассмотрим следующую проблему, состоящую из трех частей.Учитывая целые числа a1 ... an, мы хотим определить, можно ли разбить {1 ... n} на три непересекающихся подмножества I, J, K, таких что

sum (I) = sum (J) = сумма (K) = 1/3 * сумма (ВСЕ)

Например, для входа (1; 2; 3; 4; 4; 5; 8) ответ - да,потому что есть раздел (1; 8), (4; 5), (2; 3; 4).С другой стороны, для ввода (2; 2; 3; 5) ответ - нет.Разработать и проанализировать алгоритм динамического программирования для 3-PARTITION, который выполняется во многочлене времени по n и (Sum a_i)

Как я могу решить эту проблему?Я знаю 2-раздел, но все еще не могу решить

Answer 1

Простое обобщение решения с двумя наборами для случая с тремя наборами.

В исходной версии вы создаете массив логических значений sums, где sums[i] сообщает, можно ли достичь суммы i с помощью чиселиз набора или нет.Затем, когда массив создан, вы просто видите, является ли sums[TOTAL/2] true или нет.

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

В случае с 3 разделами вы сохраняете массив логических значений sums, где sums[i][j] говоритможет ли первый набор иметь сумму i, а второй - сумму j.Затем, когда массив создан, вы просто видите, если sums[TOTAL/3][TOTAL/3] равно true или нет.

Если исходная сложность равна O(TOTAL*n), то здесь O(TOTAL^2*n).
Возможно, она не является полиномиальнойв самом строгом смысле слова, но тогда оригинальная версия тоже не является строго полиномиальной:)

Answer 2

Я думаю, что при сокращении это выглядит так:

Сокращение 2-х секций до 3-х секций:

Пусть S - исходный набор, а A - его общая сумма, затем пусть S«= объединение ({А / 2}, S).Следовательно, выполнение 3-разбиения на множестве S 'дает три множества X, Y, Z. Среди X, Y, Z один из них должен быть {A / 2}, скажем, это множество Z, тогда X и Y является2-разбиение.Свидетели 3-разделов на S 'являются свидетелями 2-разделов на S, таким образом, 2-разделение сводится к 3-разделам.

Answer 3

Если эта проблема должна быть решаема;тогда sum(ALL)/3 должно быть целым числом.Любое решение должно иметь SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3.Это решение 2-х секционной проблемы над concat(ALL, {sum(ALL)/3}).

Вы говорите, что у вас есть 2-х секционная реализация: используйте ее для решения этой проблемы.Тогда (по крайней мере) один из двух разделов будет содержать число sum(ALL)/3 - удалите номер из этого раздела, и вы нашли I.Для другого раздела снова запустите 2-раздел, чтобы разделить J от K;в конце концов, J и K должны быть равны в сумме.

Редактировать: Это решение, вероятно, неверно - 2-секция объединенногомножество будет иметь несколько решений (по крайней мере, одно для каждого из I, J, K) - однако, если есть другие решения, тогда «другая сторона» может не состоять из объединения двух из I, J, K и можетне разделяться на всех.Боюсь, вам нужно подумать: -).

Попробуйте 2: Выполните итерацию по мультимножеству, поддерживая следующую карту: R(i,j,k) :: Boolean, которая представляеттот факт, что до текущей итерации числа допускают деление на три мультимножества с суммами i, j, k.То есть для любого R(i,j,k) и следующего числа n в следующем состоянии R' он содержит R'(i+n,j,k) и R'(i,j+n,k) и R'(i,j,k+n).Обратите внимание, что сложность (в соответствии с размером упражнения) зависит от величины от введенных чисел;это псевдополиномиальный алгоритм времени.Решение Nikita концептуально аналогично, но более эффективно, чем это решение, поскольку оно не отслеживает сумму третьего набора: это не нужно, поскольку его можно вычислить тривиально.

Answer 4

Вам действительно нужен полный алгоритм Карфаркара-Карпа Корфа (http://ac.els -cdn.com / S0004370298000861 / 1-s2.0-S0004370298000861-main.pdf , http://ijcai.org/papers09/Papers/IJCAI09-096.pdf). Обобщение дается три разбиения. Алгоритм на удивление быстр, учитывая сложность задачи, но требует некоторой реализации.

Основная идея KK состоит в том, чтобы большие блоки одинакового размера появлялись в разных разделах. Один группирует пары блоков, которые затем можно рассматривать как меньший размерный блок, равный разнице в размерах, которая может быть размещена как обычно: делая это рекурсивно, можно получить небольшие блоки, которые легко разместить. Затем выполняется двойная раскраска групп блоков, чтобы обеспечить обработку противоположных размещений. Расширение до 3 разделов немного сложнее. Расширение Korf заключается в использовании поиска в глубину в KK, чтобы найти все возможные решения или быстро найти решение.

Answer 5

Допустим, вы хотите разбить набор $X = {x_1, ..., x_n}$ на $k$ разделов. Создайте таблицу $ n \ times k $. Предположим, что стоимость $M[i,j]$ равна максимальной сумме $i$ элементов в $ j $ разделах. Просто рекурсивно используйте следующий критерий оптимальности для его заполнения:

M[n,k] = min_{i\leq n}  max ( M[i, k-1], \sum_{j=i+1}^{n} x_i ) 

Using these initial values for the table: 

M[i,1] = \sum_{j=1}^{i} x_i  and  M[1,j] = x_j  

The running time is $O(kn^2)$ (polynomial )