Изменения

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

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

27 байт убрано, 12:58, 27 декабря 2012
Нет описания правки
'''Задача о рюкзаке''' — дано <tex>k</tex> предметов, i <tex>i-й ый</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
== Формулировка задачи ==
Дано <tex>k</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{k}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{k}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно определить набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{k}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет включен в набор, <tex> b_{i} = 0 </tex>, если предмет не включен, такой что:
1. # <tex>b_{1} w_{1}+ ... + b_{k} w_{k} \le W</tex>
2. # <tex>b_{1} p_{1}+ ... + b_{k} k_{k} </tex> максимальна.
== Варианты решения ==
'''Задачу о рюкзаке можно решить несколькими способами:'''
1. * Перебирая все подмножества набора из k предметов. Сложность такого решения <tex>O({2^{k}})</tex>.
2. * Методом [[Meet-in-the-middle|Meet-in-the-middle]][http://neerc.ifmo.ru/wiki/index.php?title=Meet-in-the-middle#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D1.80.D1.8E.D0.BA.D0.B7.D0.B0.D0.BA.D0.B5 Meet-in-the-middle]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>
3. * Метод динамического программирование. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.
== Алгоритм <tex>O(k \times W)</tex> ==
Найдем <tex>A(s, n)</tex>. Возможны 2 варианта:
1. # Если предмет <tex>s</tex> не попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n)</tex>
2. # Если <tex>s</tex> попал в рюкзак. Тогда <tex>A(s, n) = A(s-1, n-w_{s}) + p_{s}</tex>
Таким образом:
Рассмотрим входит ли <tex>k</tex> - последний предмет в рюкзак. Если <tex>A(k, W)</tex> равно <tex>A(k-1, W)</tex>, значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.
 
Сложность алгоритма <tex>O(kW)</tex>
== Реализация ==
Сначала генерируем <tex>А</tex>
for i = 0 ... W
A[0][i] = 0
for i = 0 ... k A[i][0] = 0 { //Первые элементы приравниваем 0} for s = 1 ... k for n = 0 ... W { //Перебираем для каждого s, все n} if n >= w[s] { //Если текущий предмет можно положить в рюкзак} A[s][n] = max(A[s-1][n], A[s-1][n-w[s]]+p[s]) {//выбираем класть его или нет}
else
A[s][n] = A[s-1][n] {//иначе, не кладем}
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
void findAns(s, n)
if A[s][n] == 0
return
findAns(s-1, n - w[s]);
ans.push(s);
 
Сложность алгоритма <tex>O(kW)</tex>
== Пример ==
297
правок

Навигация