Изменения

Перейти к: навигация, поиск

Задача о рюкзаке

951 байт убрано, 10:54, 22 декабря 2012
Нет описания правки
== Пример ==
<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>s = 1</tex>. То есть можно использовать В первой строке как только первый предмет, у которого <tex>w_1 = 6, p_1 = 5вместимость рюкзака </tex>.  <tex>A(1,n) = 0</tex> при <tex>n \le 5</tex>,  <tex>A(1,n) = 5</tex> при <tex> n \ge 6 </tex>, так как <tex>w_1 \le n</tex> Рассмотрим строку <tex>s=2</tex>. То есть можно использовать первые 2 предмета. <tex>w_1 = 6, p_1 = 5</tex>  <tex>w_2 = 4, p_2 = 3</tex>  <tex>A(2, n) = A(1,n)</tex>, при <tex>n \le 3</tex>, так как нельзя положить добавляем в рюкзак <tex>2</tex> 1 предмет.  <tex>A(2,n) = max(A(1,n), A(1,n-w_{2}) + p_{2})</tex>, при остальных <tex>n</tex>. А именно: <tex>A(2,4) = max(0, 0 + 3) = 3</tex> <tex>A(2,5) = max(0, 0 + 3) = 3</tex> <tex>A(2,6) = max(5, 0 + 3) = 5</tex> <tex>A(2,7) = max(5, 0 + 3) = 5</tex> <tex>A(2,8) = max(5, 0 + 3) = 5</tex> <tex>A(2,9) = max(5, 0 + 3) = 5</tex>
Во второй строке, когда можно использовать первые <tex>A(2,10) = max(5, 5 + 3) = 8</tex>предмета.
<tex>A(2,11) = max(5, 5 + 3) = 8</tex>
<tex> ... </tex>
Максимальная стоимость рюкзака находится в <tex>A(5, 15)</tex>.
297
правок

Навигация