Изменения
Нет описания правки
== Варианты решения ==
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>
#<tex>A(k,s) = A(k-1, s)</tex>
'''Восстановим набор предметов, входящих в рюкзак'''
Будем определять , входит ли <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>
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]);
В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.
