Тройная перегородка (пример динамического программирования)

Question

У меня есть массив int, который содержит цифры, такие как {47, 94, 79, 90, 89, 14, 82, 92}. Массив должен быть разделен на три подматрицы, чтобы сумма каждого массива была минимально возможной, ака минимальной. Я думаю, что его стоит решить с помощью рекурсии, однако подход ускользает от меня, я также думал об использовании qsort в исходном массиве, а затем делил его «жадно», но он не работает все время (например, принимая самое низкое и самое высокое число и т. Д.)).

Например вышеуказанные цифры будут разделены на: 1) {94, 90, 14} 2) {92, 89} 3) {82, 79, 47}

Здесь третий массив содержит самую высокую минимальную сумму, которая 208. Порядок чисел не имеет значения. Вопрос заключается в том, как правильно разделить числа на три группы, чтобы они составляли самую низкую сумму. Нужно ли мне проверять все возможности?

Answer 1

Описанная проблема может быть смоделирована с использованием динамического программирования. Мы можем определить пространство состояний следующим образом.

v[i,t1,t2] := minimal load in partition 3 attainable for items 
       in {0,...,i} where the total load in partition 1 
       is exactly t1 and the total load in t2 is exactly t2 
       if such a load exists and positive infinity otherwise 

Для пространства состояний, i в {0,...n} и t1, t2 в {0,...,P}, где P это общая сумма элементов, которая представляет собой верхнюю границу для объективного значения и ограничена n*smax, где smax является наибольшей величиной, имеющейся на входе.

Мы получаем следующее рекуррентное соотношение, в котором случаи в основном зависят от итеративного выбора для каждого элемента, в который назначен раздел, где s_i обозначает размер i-й элемент.

v[i,t1,t2] = min { v[i-1,t1-s_i,t2], 
        v[i-1,t1,t2-s_i], 
        v[i-1,t1,t2] + s_i } 

Первый член в минимальном выражении соответствует присвоению элемента i в раздел 3, второй случай соответствует назначая элемент i в раздел 2, а третий случай соответствует назначая элемент i в раздел 3. После пространство состояний заполняется, то желаемый результат (а именно минимальная максимальная нагрузка раздела) может быть получен путем оценки следующего выражения.

Result = min { max { t1, t2, v[n,t1,t2] : t1, t2 in {0,...,P} } } 

В максимальном выражении выше, t1 бы соответствует нагрузке в группе 1, t2 бы соответствует нагрузке в разделе 2, а значение состояния v[n,t1,t2] соответствует нагрузке в разделе 3. Время работы алгоритм эскиза может быть ограничен O(n^3*smax), что является псевдополиномиальной границей времени выполнения. Если дополнительно требуется оптимальное назначение элементов в разделе, необходимо использовать либо обратную трассировку, либо вспомогательные структуры данных.

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

sum_{j=1}^{i} s_i - (t1 + t2) 

, но это не так, как указано выше количество только определяет нагрузку в разделе 3 если такое назначение действительно существует; в определении пространства состояний использование положительной бесконечности указывает на несуществование такого присвоения.

Подход очень похож на описанный here, стр. 12 ff. В целом описанную проблему можно рассматривать как проблему планирования, а именно минимизацию разметки трех идентичных параллельных машин. В так называемом three-field notation проблема обозначается как P3||Cmax, что означает, что число машин не является частью ввода, но фиксировано.