1632
правки
Изменения
м
Тогда ответом на задачу будет минимум среди всех <tex>dp[i + 1][j] = \maxmin(dp[i][j] + p_2[i + 1], dp[ni][j- p_1[i + 1]])</tex>.
Так же Тогда ответом на задачу будет <tex>\min\limits_{j}(\max(j, dp[n][j]))</tex>. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ {{---}} это максимум из этих двух величин. И в конце из всех времен выбираем минимальное. Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex> O(maxTime)</tex>.
rollbackEdits.php mass rollback
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
Задача <tex>R2 \mid \mid C_{max}</tex> является [[Классы_NP_и_Σ₁#def1|<tex>\mathrm{NP}</tex>-полной задачей]]. Доказательство смотри в книге<ref>* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.</ref>.
==Неэффективное решение==
Допустим мы посчитали динамику для <tex>i</tex> работ. Теперь надо пересчитать её для <tex>(i + 1)</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить на втором станке при фиксированном времени на первом. Так как <tex>(i + 1)</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex> dp[i + 1][j]</tex> надо прорелаксировать значением <tex>dp[i][j - p_1[i + 1]] </tex>, что соответсвует выполнению работы на первом станке, и значением <tex> dp[i][j]+p_2[i + 1]</tex> (выполнение на втором станке).
Таким образом: <tex>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex>
==Доказательство корректности алгоритма==
==Псевдокод==
<font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font>
'''function''' getCmax(n : int, p1 : '''int'''[n], p2 : '''int'''[n]): '''int''' '''int ''' maxTime = 0 '''for''' i = 0 .. n - 1:
maxTime += p1[i]
'''int'''[][] dp
fill(dp, <tex>\infty</tex>)
dp[0][0] = 0
'''for''' i = 0 .. n - 1: '''for''' j = 0 .. maxTime:
dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1])
'''int ''' answer = <tex>\infty</tex> '''for''' j = 0 .. maxTime:
answer = min(answer, max(j, dp[n][j]))
'''return''' answer
