Изменения
Нет описания правки
'''Восстановим набор предметов, входящих в рюкзак'''
Будем определять входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с вместимостью элемента <tex>A(i,w)</tex> в искомый набор, начиная с где <tex>i = N</tex>-ого предмета и вместимостью , <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:
#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i </tex> меньше и набором допустимых предметов <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> не входит в искомый набор, иначе входит.
A[i][0] = 0 //Первые элементы приравниваем 0
for k = 1..N
for s = 0..W //Перебираем для каждого sk, все nвместисмости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]) //выбираем класть его или нет
