Изменения

Будем определять входит ли <tex>n_i </tex> предмет с вместимостью <tex>w </tex> в искомый набор, начиная с <tex>N</tex>-ого предмета и вместимостью <tex>W</tex>. Для этого сравниваем <tex>A(i,w) </tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>#Максимальная стоимость рюкзака с вместимостью на w_i меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\} </tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A </tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w) </tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i </tex> не входит в искомый набор, иначе входит.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s] </tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимоси третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Начиная с <tex>A(5, 13) </tex> восстанавливаем ответ.