40
правок
Изменения
→Реализация
'''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> предметов, входящих в рюкзак, рекурсивной функцией:
'''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)
