317
правок
Изменения
→Первый случай
Работа <tex>j</tex> начинается после <tex>C(S \setminus \{j\})</tex>.
Рассмотрим два подслучая, для : <# <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> и <br> В этом случае <tex>C(S \setminus \) = r_{j\}) > r_+ p_{j}</tex>.# В первом случае <tex>C(S) = r_\setminus \{j\} + p_) > r_{j}</tex># Во втором работы <br>Работы из <tex>C(S \setminus \{j\})</tex> обрабатываются непрерывно в интервале <tex>[r_{j}, C(S \setminus \{j\})]</tex>, потому что иначе <tex>j</tex> начнет обрабатываться до <tex>C(S \setminus \{j\})</tex>.
Делаем вывод, что <tex>C_{j} (r, w) = \max(r_{j} , C(S \setminus \{j\}) + p_{j}</tex>. Предположим, что <tex>C(S \setminus \{j\})</tex> такое, что <tex>C(S \setminus \{j\}) = C_{j - 1}(r, w - w_{j})</tex> и, если это не так, заменим <tex>C(S \setminus \{j\})</tex> на выполнимое подмножество из <tex>1 \ldots j - 1</tex> для которого это выполняется. Из этого следует, что
