58
правок
Изменения
Нет описания правки
Сложность алгоритма <tex>O(NW^2)</tex>.
=== Реализация ===
Сначала генерируем <tex>A</tex>.
for i = 0..W
A[0][i] = 0
for i = 0..N
A[i][0] = 0 //Первые элементы приравниваем 0
for k = 1..N
for s = 0..W //Перебираем для каждого k, все вместисмости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]) //выбираем класть его или нет
else
A[k][s] = A[k-1][s] //иначе, не кладем
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s)
if A[k][s] == 0
return
if A[k-1][s] == A[k][s]
findAns(k-1, s)
else
findAns(k-1, s - w[k]);
ans.push(k);
