58
правок
Изменения
→Метод динамического программирования
Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.
Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
