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