Викиучебник

Реализации алгоритмов/Комбинаторика/Задача о ранце: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 31:
 
==Задача о ранце с возможностью единичного выбора предмета==
===Решение===
Обозначим через <math> K_{w,i} </math> максимальную стоимость, которую мы можем набрать при весе не более <math> w </math> среди <math> i </math> первых предметов. Получаем следующее рекуррентное соотношение:
* <math> K_{0, i} = 0, \quad 0 \le i \le n </math>
* <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>
 
===Реализация===
 
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Комбинаторика/Задача_о_ранце