Изменения
Нет описания правки
== Метод динамического программирования ==
Пронумеруем предметы по порядку, как дано в условии <tex>k=\{k_1, k_2,...,k_n. Пусть <tex>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
<tex>A(s, 0) = 0</tex>
for s = 1..k
for n = 0..W //Перебираем для каждого s, все n
if n >= w[s] //Если текущий предмет можно положить вмещается в рюкзак
A[s][n] = max(A[s-1][n], A[s-1][n-w[s]]+p[s]) //выбираем класть его или нет
else
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.
'''Теперь восстановим набор Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
Будем начиная с ячейки, соответствующей ответу, то есть вместимость <tex> = W</tex>, и можно использовать для составления набора все предметы, определять, входит последний предмет в набор или нет. Для этого сравниваем значение в рассматриваемой ячейке с:
# Со значением в ячейке с такой же вместимостью, и можно использовать все предметы имеющие
