Реализации алгоритмов/Комбинаторика/Задача о ранце: различия между версиями
Содержимое удалено Содержимое добавлено
Vlsergey (обсуждение | вклад) Новая страница: «===Реализация=== C++ <source lang="cpp"> #include <vector> #include <limits> //wts - массив весов, cost - массив стоимост…» |
|||
Строка 32:
===Решение===
Обозначим через <math> K_{w,i} </math> максимальную стоимость, которую мы можем набрать при весе не более <math> w </math> среди <math> i </math> первых предметов. Получаем следующее рекуррентное соотношение:
* <math> K_{0,
* <math> K_{w, 0} = 0, \quad 0 \le w \le W </math>
* <math> K_{w, i} = \begin{cases} \max{ \left( K_{w, i - 1}, K_{w-w_i, i - 1} + v_{i} \right) }, \quad w_i \le w \\ K_{w, i - 1}, \quad w_i > w \end{cases}, 0 \le w \le W </math>
| |||