\Section{Жадность или получаем зачёты оптимальным образом}{11 декабря}{Егор Щербин}

\Subsection{Методы решения некоторых задач теории расписаний}

Решим несколько задач, в которых нужно составить расписание выполнения
некоторых абстрактных работ, которое удовлетворяет некоторым условиям и/или оптимизирует
некую величину.

\begin{THE}{$t_i$ "--- время выполнения $i$-й работы, выполнить максимальное количество работ, чтобы
            суммарное время выполнения не превышало $T$}

    Решение: отсортируем работы по $t_i$ и будем набирать, начиная с меньших, пока возможно. $\O(Sort)$.

    Набросок доказательства: можно заменить работу с большим $t_i$ на меньшее.

    \textit{Замечание:} можно за $\O(n)$ модифицированным алгоритмом поиска порядковой статистики.
\end{THE}

\begin{THE}{$t_i$, $d_i$ "--- дедлайн (максимальный момент времени, до которого нужно закончить выполнение работы),
            можно ли выполнить все работы}

    Решение: нужно пробовать выполнять все работы в порядке увеличения дедлайна.

    Доказательство: пусть есть какой-то корректный порядок выполнения (если он есть), тогда в 
                    нём можно переместить работу с минимальным дедлайном в начало списка выполнения.
                    Действительно, идущие перед ней работы теперь будут заканчиваться не позже,
                    чем заканчивалась она, но её дедлайн "--- минимальный, поэтому все работы
                    все ещё можно выполнить. Дальше делаем аналогично.
\end{THE}

\begin{THE}{$t_i$, $d_i$ "--- дедлайн, но не конца, а начала времени выполнения}

    Решение: отсортировать в порядке увеличения $(t_i+d_i)$.

    Доказательство: очевидное доказательство "--- свести к предыдущей задаче. Тем не менее, для
                    расширения сознания, приведём другой способ решения этой задачи. Пусть $j$-я
                    работа выполняется последней. Тогда $(\sum t_i)-t_j\le d_j\SO CONST \le t_j+d_j$.
                    Тогда заведомо не хуже выбрать в качестве последней работы ту, у которой $(t_i+d_i)$
                    максимально.
\end{THE}

\begin{THE}{$t_i$, $fee_i>0$ "--- штраф, минимизировать $\sum T_i\cdot fee_i$, где $T_i$ "--- момент окончания
            выполнения $i$-й работы}

            Решение: выполнять работы в порядке уменьшения $\dfrac{fee_i}{t_i}$.
            
            Доказательство: возьмём произвольный порядок выполнения работ, пусть есть две соседние работы 
            $A$ и $B$ ($A$ прямо перед $B$), такие что $\dfrac{fee_A}{t_A}<\dfrac{fee_B}{t_B}\SO t_B fee_A<t_Afee_B$, 
            тогда рассмотрим,
            как поменяется целевая функция если поменять эти две работы местами:
                $$t_A\cdot fee_A+(t_A+t_B)\cdot fee_B + CONST\to t_B fee_B+(t_A+t_B)fee_A + CONST$$
                $$t_Afee_B\to t_Bfee_A$$
            Значит, таким действием мы только улучшим ответ.

            Чтобы доказательство методом $swap$-ов работало, нужно доказать, что при равенстве сравниваемых
            величин (в нашем случае $\dfrac{fee_i}{t_i}$) не важно, в каком порядке идут работы $A$ и $B$. 
            В данной задаче это очевидно.
\end{THE}

\begin{trivlist}
\item
\end{trivlist}

Многие задачи, подобные рассмотренным, решаются сортировкой работ в соответствии с некоторые
компаратором $less(a,b)$, который проверяет, правда ли выгоднее поставить работу $a$ перед работой $b$.
Более того, этот компаратор имеет вид
\begin{code}
    less(a, b): return F(a, b) < F(b, a)
\end{code}
, где $F(a,b)$ "--- какая-то ``величина оптимальности'', если поставить $a$ перед $b$.

Например, решим третью задачу про дедлайн начала таким способом.

Пусть есть две соседние задачи $A$ и $B$, а суммарное время выполнения всех задач перед ними равно $T$.
Если задача $A$ идёт перед задачей $B$, то должны выполняться условия $T\le d_A$ и $T+t_A\le d_B$, то есть
$T\le \min(d_A,d_B-t_A)$. Аналогично, если $B$ идёт перед $A$, то $T\le \min(d_B,d_A-t_B)$. Видно, что
выгоднее выбрать такой вариант, в котором ограничение сверху на $T$ как можно более свободное, то есть
тот, у которого соответствующий минимум максимален.

К сожалению, на паре не было времени, чтобы показать, что такой порядок транзитивен.

\Subsection{Задача о двух станках или $F_2||C_{max}$}

Есть два станка и несколько деталей, каждую из которых нужно обработать сначала на первом
станке, а затем на втором. Время обработки $i$-й детали на первом станке равна $a_i$, а на
втором "--- $b_i$. Необходимо минимизировать момент завершения обработки всех деталей.

Утверждение: выполнять работы на обоих станках надо в одном и том же порядке. Действительно, пусть
какой-то префикс работ на обоих станках совпадает, а затем на втором станке обрабатывается $i$-я деталь.
Тогда можно и на первом станке $i$-ю деталь обрабатывать сразу после найденного префикса (все детали,
которые сдвинулись на первом станке всё равно будут обработаны, так как они обрабатываются после $i$-й). 
Тем самым мы увеличим префикс. Такими действиями дойдём до того, что порядок обработки деталей на обоих станках одинаков.

Рассмотрим две соседние в этом порядке детали $x$ и $y$. На минутку забудем, что есть другие детали. Рассмотрим 
время выполнения этих работ, оно равно $a_x+\max(a_y,b_x)+b_y$ (через $\max(a_y,b_x)$ единиц времени сможет начать
обрабатываться на втором станке деталь $y$). $a_x+b_y+max(a_y,b_x)=a_x+b_y+min(a_y,b_x)+max(a_y,b_x)-min(a_y,b_x)=
a_x+a_y+b_x+b_y-min(a_y,b_x)$. Теперь наш компаратор принимает вид:
\begin{code}
    less(x,y): return min(a_y,b_x) > min(b_y,a_x)
\end{code}

В общем случае, нужно рассмотреть несколько случаев, чтобы показать, что, следуя данному компаратору, выгодно
обменять (или не обменивать) две соседние детали местами.

Опять же, окончательное доказательство корректности такого алгоритма приведено не было, либо автор не помнит такого.

\Subsection{Задача о выполнении максимального количества работ}

Рассмотрим ещё одну задачу: есть несколько работ, у каждой своё время выполнения $t_i$ и дедлайн $d_i$, но теперь
нужно не проверить, можно ли выполнить их все, а выполнить как можно больше из них.

Сперва отсортируем все задачи по возрастанию $d_i$, как было в прошлой задаче. Теперь рассмотрим два решения.
Первое работает медленнее и вряд ли пригодится нам с практической точки зрения, но оно поможет доказать второе.

\begin{THE}{Решение динамическим программированием.}
    Рассмотрим первые $i$ работ и все способы выбрать ровно $k$ из них, чтобы все $k$ можно было выполнить. Тогда
    пусть $T[i,k]$ "--- минимальное по всем таким способам суммарное время выполнения этих $k$ работ ($T[i,k]=+\infty$,
    если таких способов нет). Теперь рассмотрим $(i+1)$-ю работу и прорелаксируем динамику. Либо мы оставляем эту
    работу в покое ($relax(T[i+1,k],T[i,k])$), либо мы выполняем её ($relax(T[i+1,k+1],T[i,k]+t_{i+1})$), но это возможно
    только при условии $T[i,k]+t_{i+1}\le d_{i+1}$. Ответ "--- максимальное $k$, такое что $dp[n][k]\ne+\infty$.
\end{THE}

\begin{THE}{Жадное решение.}
    Опять же будем рассматривать работы по очереди и для каждого префикса работ строить оптимальное решение определенным образом.
    Пусть мы построили какой-то ответ и рассматриваем $i$-ю работу. Есть три случая:

    \begin{enumerate}
    \item
        Если мы можем добавить её к текущему ответу, то есть $S+t_i\le d_i$, где $S$ "--- суммарное время выполнения выбранных работ,
        то просто делаем это.
    \item
        Иначе пробуем качественно улучшить текущий ответ. Если существует среди выбранных такая работа, что её время выполнения больше,
        чем $t_i$, то мы можем избавиться от этой работы, а взамен неё поставить $i$-ю. Ясно, что новый набор работ тоже можно выполнить.
        (\textit{Реализационное замечание: здесь надо использовать кучу})
    \item
        Иначе ничего не происходит.
    \end{enumerate}

    Пусть на $i$-м шаге $k_i$ "--- количество выбранных работ, а $a_1\le a_2\le\ldots\le a_{k_i}$ "--- отсортированные времена выполнения выбранных работ.
    Утверждается, что $k_i$ "--- максимальное $k$, такое что $T[i,k]\ne+\infty$, и что $T[i,m]=\sum\limits_{t=1}^ma_t$. Из этого утверждения, в
    частности, очевидным образом следует коррекность алгоритма.

    Докажем его по индукции.

    \begin{THEE}{База:}
        $i=0\SO k=0$.
    \end{THEE}

    \begin{THEE}{Переход: $i\to i+1$}
        \begin{enumerate}
        \item
            Пусть $OPT_j$ "--- оптимальный ответ на $j$-м шаге. Знаем, что $OPT_i=k_i$. Надо доказать, что $OPT_{i+1}=k_{i+1}$. 
            Если $OPT_{i+1}=OPT_i$, то наш алгоритм не мог улучшить ответ, поэтому всё хорошо. Если $OPT_{i+1}>OPT_{i}$, то,
            во-первых, $(i+1)$-я работа точно должна быть выполнена (иначе $OPT_i=OPT_{i+1}$), и наш алгоритм её сможет взять,
            так как для неё останется времени не меньше, чем в любом оптимальном ответе (ибо $T[i,k]$ "--- минимум).
        \item
            Заметим, что $T[i+1,m]$ равно либо $T[i,m-1]+t_i$, либо $T[i,m]=T[i,m-1]+a_m$ (последнее равенство по предположению индукции).
            Теперь легко доказать, вторую часть утверждения. В зависимости от случая (1)-(3) $t_{i+1}$ как-то встраивается (или не встраивается)
            в последовательность $a_1,\ldots,a_{k_i}$, и внутренней индукцией, в которой база и переходы получаются из вышеописанного
            пересчёта динамики, показывается что сумма $m$ минимальных работ из новых выбранных равна $T[i+1,m]$.
        \end{enumerate}
    \end{THEE}
\end{THE}
