297
правок
Изменения
Нет описания правки
== Пример ==
<tex>W = 1513, k = 5</tex>
<tex>w_{1} = 63, p_{1} = 5 1 </tex>
<tex>w_{2} = 4, p_{2} = 3 6 </tex>
<tex>w_{3} = 35, p_{3} = 1 4 </tex>
<tex>w_{4} = 28, p_{4} = 3 7 </tex>
<tex>w_{5} = 59, p_{5} = 6 </tex>
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| s = 0|| 0|| 10|| 20|| 30|| 40|| 50|| 60|| 70|| 80|| 90|| 100|| 110|| 120|| 13|| 14|| 15 0
|-
| s = 01|| 0|| 0|| 0|| 01|| 0|| 0|| 01|| 01|| 01|| 01|| 01|| 01|| 01|| 01|| 01|| 01
|-
| s = 12|| 0|| 0|| 0|| 0|| 0|| 01|| 56|| 56|| 56|| 57|| 57|| 57|| 57|| 57|| 57|| 57
|-
| s = 2|| 03|| 0|| 0|| 0|| 3|| 31|| 56|| 56|| 56|| 57|| 87|| 810|| 810|| 810|| 811|| 811
|-
| s = 34|| 0|| 0|| 0|| 1|| 36|| 36|| 5|| 5|| 56|| 67|| 87|| 810|| 810|| 910|| 913|| 913
|-
| s = 45|| 0|| 0|| 3|| 3|| 3|0| 4|| 61|| 6|| 8|| 8|| 8|| 9|| 11|| 11|| 11|| 12|-| s = 5|| 0|| 0|| 3|| 3|| 3|| 6|| 6|| 97|| 97|| 910|| 10|| 12|| 12|| 1410|| 1413|| 14 13
|}
Числа от 0 до 15 в первой строчке обозначают вместимость рюкзака.
Во второй строке, когда можно использовать первые <tex>A(2,10) = max(5, 5 + 3) = 8</tex>предмета.
Максимальная стоимость рюкзака находится в <tex>A(5, 15)</tex>.
