Изменения
Нет описания правки
Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</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_{N} w_{N} \le W</tex> # <tex>b_{1} p_{1}+ ... + b_{N} k_p_{N} </tex> максимальна.
== Варианты решения ==
'''Задачу о рюкзаке можно решить несколькими способами:'''
* Перебирая Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>
== Метод динамического программирования ==
Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметовдля <tex>A(k,s)</tex>.
<tex>A(k, 0) = 0</tex>
Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:
# Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости, рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_({k-1)}\}</tex>, то есть <tex>A(k,s)</tex> = A(k-1, s)</tex> # Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимотистоимости рюкзака, где вес s уменьшаем на вес <tex>k рюкзака >/tex>-ого предмета и набор допустимых предметов <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>
Выберем из этих двух значений максимальное:
<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>
Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>. '''Восстановим набор предметов, входящих в рюкзак.'''
