58
правок
Изменения
→Метод динамического программирования
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i- 1; \\ maxmin(d(i - 1, c), d(i, c - w_i) + p_i1) & for\ c = w_i, ..., W;
\end{cases}
</tex>
После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного, и использовать формулу:
<tex> d(c) = maxmin(d(c), d(c - w_i) + p_i1) </tex> После выполнения в <tex> d(N\ \ \ for\ c = w_i, ...,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.
Сложность алгоритма <tex>O(NW)</tex>.
