212
правок
Изменения
Нет описания правки
Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти до <tex dpi=130> \sum{p_{1}[i]}</tex>.
==Корректность==
Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное. Пусть в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.
Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер <tex>i</tex>. Если её выполнить на первом станке, то время окончания всех работ будет <tex>\max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>. Однако <tex>\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>
Рассмотрим произвольную работу, выполненную в оптимальном расписании на втором станке, но на первом в расписании, составленном алгоритмом. Пусть номер этой работы <tex>j</tex>. Если выполнять эту работу на втором станке, то время выполнения всех работ будет <tex>\max(time - p_{1}[j], d[n][time - p_{1}[j]])</tex>. Но <tex> \max(time, d[n][time]) \leqslant \max(time - p_{1}[j], d[n][time - p_{1}[j]]) </tex>.
В итоге если превратить решение <tex>S</tex> в решение <tex>S'</tex> эквивалентное <tex>O</tex>, то ответ <tex>S</tex> не будет превосходить ответ <tex>S'</tex>. Тогда расписание <tex>S</tex> оптимальное.
==Псевдокод==
