R2Cmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эффективное решение)
(Эффективное решение)
Строка 17: Строка 17:
 
Применим для решения данной задачи динамическое программирование.
 
Применим для решения данной задачи динамическое программирование.
  
Будем  считать <tex>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> с каким временем выполнения работ на первом станке.
+
Будем  считать <tex>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке.
  
Изначальное значение <tex>dp[0][0] = 0</tex>.
+
Изначальное значение <tex>dp[0][0] = 0</tex>, а всё остальную таблицу проинициализируем бесконечностью.
 +
 
 +
Допустим мы посчитали динамику для <tex>i-1</tex> работ. Теперь надо пересчитать её для <tex>i</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как <tex>i</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex>dp[i][j]=  \min(dp[i-1][j-p_1[i]], dp[i-1][j]+p_2[i])</tex>.
 +
 
 +
Тогда ответом на задачу будет минимум среди всех максимумов из <tex>j</tex> и <tex>dp[n][j]</tex>.

Версия 20:48, 20 июня 2012

Эта статья находится в разработке!


Постановка задачи

Дано два разных неоднородных станка, которые работают параллельно. Есть [math]n[/math] работ, время выполнения которых на первом и втором станке различное. Нужно минимизировать время завершения всех работ.

Сложность задачи

Задача [math]R2 \mid \mid C_{max}[/math] является [math]\mathrm{NP}[/math]-полной задачей.

Неэффективное решение

Переберём все битовые последовательности из [math]n[/math] элементов. Для каждой перестановки вычислим завершение последней работы. Работы будем выполнять следующим образом, если на [math]i[/math] -й позиции стоит 0, то [math]i[/math] -ая работа будет выполняться на первом станке, иначе на втором. Среди всех перестановок выберем ту перестановку, у которой [math]C_{max}[/math] минимальный.

Время работы алгоритма [math]O(n \cdot 2^n)[/math]

Эффективное решение

Применим для решения данной задачи динамическое программирование.

Будем считать [math]dp[i][j][/math], в котором будем хранить минимально время выполнения работ на втором станке, где [math]i[/math] означает, что мы рассмотрели [math]i[/math] работ, а [math]j[/math] с каким временем выполнения работ на первом станке. Тогда [math]j[/math] не превосходит суммы выполнения работ на первом станке.

Изначальное значение [math]dp[0][0] = 0[/math], а всё остальную таблицу проинициализируем бесконечностью.

Допустим мы посчитали динамику для [math]i-1[/math] работ. Теперь надо пересчитать её для [math]i[/math]-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как [math]i[/math]-ю работу мы можем выполнить либо на первом станке, либо на втором, то [math]dp[i][j]= \min(dp[i-1][j-p_1[i]], dp[i-1][j]+p_2[i])[/math].

Тогда ответом на задачу будет минимум среди всех максимумов из [math]j[/math] и [math]dp[n][j][/math].