317
правок
Изменения
→Идея
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое <tex> \wedge r(S) \geqslant r \wedge 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>
