Изменения
Нет описания правки
#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</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>
Если короче:
'''Восстановим набор предметов, входящих в рюкзак'''
Будем определять входит ли n_i предмет с вместимостью w в искомый набор, начиная с N-ого предмета и вместимостью W. Для этого сравниваем A(i,w) со следующими значениями:
#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов \{n_1,n_2,...,n_{i-1}\}, то есть A(i-1, w)
#Максимальная стоимость рюкзака с вместимостью на w_i меньше и набором допустимых предметов \{n_1,n_2,...,n_{i-1}\} плюс стоимость p_i, то есть A(i-1, w-w_i)+p_i
Заметим, что при построении A мы выбирали максимум из этих значений и записывали в A(i, w). Тогда будем сравнивать A(i, w) c A(i-1, w), если равны, тогда n_i не входит в искомый набор, иначе входит.
== Реализация ==
Сначала генерируем <tex>A</tex>.
for i = 0..W
A[0][i] = 0
for i = 0..kN
A[i][0] = 0 //Первые элементы приравниваем 0
for s k = 1..k N for n s = 0..W //Перебираем для каждого s, все n if n s >= w[sk] //Если текущий предмет вмещается в рюкзак A[sk][ns] = max(A[sk-1][ns], A[sk-1][ns-w[sk]]+p[sk]) //выбираем класть его или нет
else
A[sk][ns] = A[sk-1][ns] //иначе, не кладем
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
findAns(k, s, n) if A[sk][ns] == 0
return
if A[sk-1][ns] == A[sk][ns] findAns(sk-1, ns)
else
findAns(sk-1, n s - w[sk]); ans.push(sk);
Сложность алгоритма <tex>O(kWN \times W)</tex>
== Пример ==
<tex>W = 13, k N = 5</tex>
<tex>w_{1} = 3, p_{1} = 1 </tex>
| || 0|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12|| 13
|-
| s k = 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0
|-
| s k = 1|| 0|| 0|| 0|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1|| 1
|-
| s k = 2|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 7|| 7|| 7|| 7|| 7
|-
| s k = 3|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 11|| 11
|-
| s k = 4|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 13|| 13
|-
| s k = 5|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 13|| 13
|}
Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.
В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.
'''Картинка''' Рассмотрим <tex>s k = 3</tex>, при каждом <tex>n s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[sk-1][ns] и A[sk-1][ns-w_3]+p_3</tex> и записываем в <tex>A[sk][ns]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимость стоимоси третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.
Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
'''Картинка'''
Таким образом, набор состоит из <tex>1, 2, 54</tex> предметов.
Стоимость рюкзака <tex>= 5 6 + 3 + 6 7 = 1413</tex>
Вес рюкзака <tex>= 6 + 4 + 5 8 = 1512</tex>
== Литература ==
