Изменения

== Алгоритм ==

1. Перебирая все подмножества набора из k предметов. Сложность такого решения <tex>O({2^{k}})</tex>.

3. Метод динамического программирование. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.

Пусть <tex>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.

Сначала генерируем <tex>А</tex>

for (i = 0; i <= W; ++i):

A[0][i] = 0

for (n = 0; n <= W; ++n): {Перебираем для каждого s, все n}

if n >= w[s] {Если текущий предмет можно положить в рюкзак}

else A[s][n] = A[s-1][n] {иначе, не кладем}

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

if A[s][n] == 0

then return

if A[s-1][n] == A[s][n]

else

ans.push(s);

== Пример ==

Максимальная стоимость рюкзака находится в <tex>A(5, 15)</tex>.

Сравниваем <tex>A(5, 15) = 14</tex> и <tex>A(4, 15) = 12</tex>. Не равны. Следовательно, <tex>5</tex> предмет входит в искомый набор, переходим к <tex>4</tex> предмету с весом рюкзака <tex>W - w_5</tex>. То есть <tex>15 - 5 = 10</tex>