'''Задача о рюкзаке''' — дано <tex>kN</tex> предметов, <tex>k_in_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
== Формулировка задачи ==
Дано <tex>kN</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{kN}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{kN}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно определить найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{kN}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:
# <tex>b_{1} w_{1}+ ... + b_{kN} w_{kN} \le W</tex>
# <tex>b_{1} p_{1}+ ... + b_{kN} k_{kN} </tex> максимальна.
== Варианты решения ==
'''Задачу о рюкзаке можно решить несколькими способами:'''
* Перебирая все подмножества набора из k N предметов. Сложность такого решения <tex>O({2^{kN}})</tex>.
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>
* Метод динамического программирования. Сложность - <tex>O(k N \times W)</tex>.
== Метод динамического программирования ==
Пронумеруем предметы по порядкуПусть <tex>A(k, как дано s)</tex> есть максимальная стоимости предметов, которые можно уложить в условии рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k=</tex> предметов, то есть <tex>\{k_1n_1, k_2n_2,...,k_nn_k\}</tex>, назовем этот набор допустимых предметов. Пусть <tex>A(k, 0) = 0</tex> <tex>A(0, s) = 0</tex> Найдем <tex>A(k, s)</tex>. Возможны 2 варианта: # Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, ns)</tex> есть максимальная равно максимальной стоимости , с такой же вместимостью и набором допустимых предметов<tex>\{n_1,n_2,..., которые можно уложить n_(k-1)\}</tex>, то есть <tex>A(k,s)</tex> = A(k-1, s)</tex> # Если <tex>k</tex> попал в рюкзак вместимости n. Тогда <tex>A(k, s)</tex> равно максимальной стоимоти, если можно использовать только первые s предметов где вес s уменьшаем на вес k рюкзака и набор допустимых предметов <tex>\{n_1,n_2,...,n_(k-1)\}</tex> плюс стоимость <tex>k рюкзака, то есть <tex>A(k-1, s-w_k) + p_k</tex> Если короче: # <tex>A(k,s) = A(k-1, s)</tex> # <tex>A(k,s) = A(k-1, s-w_k) + p_k</tex> Выберем из заданных kэтих двух значений максимальное: <tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex> '''Восстановим набор предметов, входящих в рюкзак.'''
<tex>A(s, 0) = 0</tex>
<tex>A(0, n) = 0</tex>
Найдем <tex>A(s, n)</tex>. Возможны 2 варианта:
# Если предмет <tex>s</tex> не попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n)</tex>
# Если <tex>s</tex> попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n-w_{s}) + p_{s}</tex>
Таким образом:
<tex>A(s,n) = max(A(s-1,n), A(s-1,n-w_{s}) + p_{s})</tex>
Теперь найдем набор предметов, входящих в рюкзак.
Рассмотрим входит ли <tex>k</tex> - последний предмет в рюкзак. Если <tex>A(k, W)</tex> равно <tex>A(k-1, W)</tex>, значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.
== Реализация ==
