Изменения

Задача <tex>R2 \mid \mid C_{max}</tex> является [[Классы_NP_и_Σ₁|<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>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> {{---}} с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке. Назовем эту сумму <tex>maxTime</tex>.

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

Таким образом:<tex>dp[i + 1][j] = \min\begin{cases} (dp[i][j] + p_2[i + 1]\\ , dp[i][j - p_1[i + 1]]\\\end{cases})</tex>

Тогда ответом на задачу будет минимум среди всех максимумов из <tex>\max(j</tex> и <tex>, dp[n][j])</tex>.

Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex dpi=130> O(\sum\limits_{i = 1}^{n} p_1[i]maxTime)</tex>.

Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное. Пусть и в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.

<font color=green>//Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>//Функция возвращает минимальное время выполнения всех работ на двух станках.</font> '''function''' getCmax(n: int, p1: int[], p2: int[]): int int maxTime = 0 '''for''' i = 0 .. n - 1: maxTime += p1[i] dp int[][] = INFdp fill(dp, <tex>\infty</tex>) dp[0][0] = 0 '''for''' i = 0 .. n - 1: '''for''' j = 0 .. maxTime '''if''' dp[i + 1][j + p1[i]] > dp[i][j]: dp[i + 1][j + p1[i]] = min(dp[i][j] '''if''' dp- p1[i + 1][j] > , dp[i][j] + p2[i]: dp[i + 1][j] = dp[i][j] + p2[i]) int answer = INF<tex>\infty</tex> '''for ''' j = 0 .. maxTime: answer = '''min'''(answer, '''max'''(j, dp[n][j])) '''return''' answer