317
правок
Изменения
→Идея
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое<tex>; r(S) \geqslant r; w(S) \geqslant w \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
Максимальный вес выполнимого множества задается максимальным значением <tex>w</tex> такого, что <tex>C_{n}(r_{\min}, w</tex> конечно, где <tex>r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}</tex>. Посчитаем значения <tex>C_{j}(r, w)</tex> за <tex>n</tex> итераций с начальными значениями
:<tex>C_{0}(r, 0) = 0</tex> для всех <tex>r</tex>
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно,
:<p>
<tex>C_{j}(r, w)
\left \{\begin{array}{ll} = C_{j - 1}(r, w) & \text{if } r > r_{j} \\
\leqslant C_{j - 1}(r, w), & \text{otherwise} \end{array} \right.
</tex>
</p>
Отсюда следует, что нам нужно посчитать только такие значения <tex>C_{j} (r, w)</tex> для которых <tex>r \leqslant r_{j}</tex>. Пусть <tex> S \subseteq \{ 1 \ldots j \} </tex> и <tex>C_{j}(r, w) = C(S)</tex>. Если <tex>j \notin S</tex>, тогда <tex>C_{j}(r, w) = C_{j - 1}(r, w)</tex>. Иначе рассмотрим два случая.
==Источники информации==
