152
правки
Изменения
Нет описания правки
Тогда ответом на задачу будет минимум среди всех максимумов из <tex>j</tex> и <tex>dp[n][j]</tex>.
==Псевдокод==
<tex>maxTime \leftarrow 0 </tex>
for <tex>i = 1 \dots n</tex>
<tex>maxTime += p_1[i]</tex>
<tex>dp[][] \leftarrow INF</tex>
<tex>dp[0][0] \leftarrow 0 </tex>
for <tex>i = 1 \dots n</tex>
for <tex>j = 0 \dots maxTime </tex>
if <tex>(j - p_2[i] > 0) </tex> then
<tex>dp[i][j] \leftarrow \min (dp[i][j], dp[i-1][j - p_1[i]) </tex>
<tex>dp[i][j] \leftarrow \min (dp[i][j], dp[i-1][j] + p_2[i])</tex>
<tex>answer \leftarrow INF</tex>
for <tex> j = 0 \dots maxTime </tex>
<tex>answer \leftarrow \min (answer, \max(j, dp[n][j]))</tex>
==Время работы==
Время работы <tex>O(n * maxTime)</tex> {{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.
==Литература==
J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity
of machine scheduling problems. Annals of Discrete Mathematics,
1:343–362, 1977.
