212
правок
Изменения
м
Нет описания правки
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
Задача <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[0][0] = 0</tex>, а всё остальную таблицу проинициализируем бесконечностью.
Допустим мы посчитали динамику для <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>
