40
правок
Изменения
→Реализация
A[0][i] = 0
'''for''' i = 0 to n
A[i][0] = 0 ''<font color="green">// Первые элементы приравниваем к 0</font>''
'''for''' k = 1 to n
'''for''' s = 1 to w ''<font color="green">//Перебираем для каждого k все вместимости</font>''
'''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>''
A[k][s] = max(A[k - 1][s], A[k - 1][s - w[k]] + p[k]) ''<font color="green">//выбираем Выбираем класть его или нет</font>''
'''else'''
A[k][s] = A[k - 1][s] ''<font color="green">//иначеИначе, не кладем</font>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
