212
правок
Изменения
Нет описания правки
и втором станке различное. Нужно минимизировать время завершения всех работ.}}
Задача <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>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex>
Тогда ответом на задачу будет минимум среди всех <tex>\min\limits_{j}(\max(j, dp[n][j]))</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
