297
правок
Изменения
Новая страница: «'''Задача о рюкзаке''' — дано <tex>k</tex> предметов, i-й предмет имеет массу <tex> w_i > 0</tex> и стоим...»
'''Задача о рюкзаке''' — дано <tex>k</tex> предметов, i-й предмет имеет массу <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. Методом [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>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
<tex>A(s, 0) = 0</tex>
<tex>A(0, n) = 0</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>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>, значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.
Сложность алгоритма <tex>O(kW)</tex>
== Реализация ==
Сначала генерируем <tex>А</tex>
<font size=3>
for (i = 0; i <= W; ++i):
A[0][i] = 0
for (i = 0; i <= k; ++i):
A[i][0] = 0 {Первые элементы приравниваем 0}
for (s = 1; s <= k; ++s):
for (n = 0; n <= W; ++n): {Перебираем для каждого s, все n}
if n >= w[s] {Если текущий предмет можно положить в рюкзак}
then A[s][n] = max(A[s-1][n], A[s-1][n-w[s]]+p[s]) {значит, выбираем, что лучше, класть его или нет}
else A[s][n] = A[s-1][n] {иначе, не кладем}
</font>
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
<font size=3>
void find_ans(int s, int n)
if A[s][n] == 0
then return
if A[s-1][n] == A[s][n]
then find_ans(s-1, n)
else
find_ans(s-1, n - w[s]);
ans.push(s);
</font>
== Пример ==
<tex>W = 15, k = 5</tex>
<tex>w_{1} = 6, p_{1} = 5 </tex>
<tex>w_{2} = 4, p_{2} = 3 </tex>
<tex>w_{3} = 3, p_{3} = 1 </tex>
<tex>w_{4} = 2, p_{4} = 3 </tex>
<tex>w_{5} = 5, p_{5} = 6 </tex>
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || 0|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12|| 13|| 14|| 15
|-
| s = 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0
|-
| s = 1|| 0|| 0|| 0|| 0|| 0|| 0|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5
|-
| s = 2|| 0|| 0|| 0|| 0|| 3|| 3|| 5|| 5|| 5|| 5|| 8|| 8|| 8|| 8|| 8|| 8
|-
| s = 3|| 0|| 0|| 0|| 1|| 3|| 3|| 5|| 5|| 5|| 6|| 8|| 8|| 8|| 9|| 9|| 9
|-
| s = 4|| 0|| 0|| 3|| 3|| 3|| 4|| 6|| 6|| 8|| 8|| 8|| 9|| 11|| 11|| 11|| 12
|-
| s = 5|| 0|| 0|| 3|| 3|| 3|| 6|| 6|| 9|| 9|| 9|| 10|| 12|| 12|| 14|| 14|| 14
|}
Числа от 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> предмет.
<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>.
Теперь восстановим набор предметов, из которых состоит максимально дорогой рюкзак.
Сравниваем <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>
Сравниваем <tex>A(4, 10) = 8</tex> и <tex>A(3, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>3</tex> предмету с тем же весом рюкзака.
Сравниваем <tex>A(3, 10) = 8</tex> и <tex>A(2, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>2</tex> предмету с тем же весом рюкзака.
Сравниваем <tex>A(2, 10) = 2</tex> и <tex>A(1, 10) = 5</tex>. Не равны. Следовательно, <tex>2</tex> предмет входит в набор, уменьшаем вес рюкзака на <tex>w_2</tex>, переходим к <tex>1</tex> предмету.
Сравниваем <tex>A(1, 6) = 5</tex> и <tex>A(0, 6) = 0</tex>. Не равны. Следовательно, <tex>1</tex> предмет входит в набор.
Таким образом, набор состоит из <tex>1, 2, 5</tex> предметов.
Стоимость рюкзака <tex>= 5 + 3 + 6 = 14</tex>
Вес рюкзака <tex>= 6 + 4 + 5 = 15</tex>
== Литература ==
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
== Формулировка задачи ==
Дано <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. Методом [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>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
<tex>A(s, 0) = 0</tex>
<tex>A(0, n) = 0</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>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>, значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.
Сложность алгоритма <tex>O(kW)</tex>
== Реализация ==
Сначала генерируем <tex>А</tex>
<font size=3>
for (i = 0; i <= W; ++i):
A[0][i] = 0
for (i = 0; i <= k; ++i):
A[i][0] = 0 {Первые элементы приравниваем 0}
for (s = 1; s <= k; ++s):
for (n = 0; n <= W; ++n): {Перебираем для каждого s, все n}
if n >= w[s] {Если текущий предмет можно положить в рюкзак}
then A[s][n] = max(A[s-1][n], A[s-1][n-w[s]]+p[s]) {значит, выбираем, что лучше, класть его или нет}
else A[s][n] = A[s-1][n] {иначе, не кладем}
</font>
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
<font size=3>
void find_ans(int s, int n)
if A[s][n] == 0
then return
if A[s-1][n] == A[s][n]
then find_ans(s-1, n)
else
find_ans(s-1, n - w[s]);
ans.push(s);
</font>
== Пример ==
<tex>W = 15, k = 5</tex>
<tex>w_{1} = 6, p_{1} = 5 </tex>
<tex>w_{2} = 4, p_{2} = 3 </tex>
<tex>w_{3} = 3, p_{3} = 1 </tex>
<tex>w_{4} = 2, p_{4} = 3 </tex>
<tex>w_{5} = 5, p_{5} = 6 </tex>
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || 0|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12|| 13|| 14|| 15
|-
| s = 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0
|-
| s = 1|| 0|| 0|| 0|| 0|| 0|| 0|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5|| 5
|-
| s = 2|| 0|| 0|| 0|| 0|| 3|| 3|| 5|| 5|| 5|| 5|| 8|| 8|| 8|| 8|| 8|| 8
|-
| s = 3|| 0|| 0|| 0|| 1|| 3|| 3|| 5|| 5|| 5|| 6|| 8|| 8|| 8|| 9|| 9|| 9
|-
| s = 4|| 0|| 0|| 3|| 3|| 3|| 4|| 6|| 6|| 8|| 8|| 8|| 9|| 11|| 11|| 11|| 12
|-
| s = 5|| 0|| 0|| 3|| 3|| 3|| 6|| 6|| 9|| 9|| 9|| 10|| 12|| 12|| 14|| 14|| 14
|}
Числа от 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> предмет.
<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>.
Теперь восстановим набор предметов, из которых состоит максимально дорогой рюкзак.
Сравниваем <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>
Сравниваем <tex>A(4, 10) = 8</tex> и <tex>A(3, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>3</tex> предмету с тем же весом рюкзака.
Сравниваем <tex>A(3, 10) = 8</tex> и <tex>A(2, 10) = 8</tex>. Равны. Следовательно, <tex>4</tex> предмет не входит в набор, переходим к <tex>2</tex> предмету с тем же весом рюкзака.
Сравниваем <tex>A(2, 10) = 2</tex> и <tex>A(1, 10) = 5</tex>. Не равны. Следовательно, <tex>2</tex> предмет входит в набор, уменьшаем вес рюкзака на <tex>w_2</tex>, переходим к <tex>1</tex> предмету.
Сравниваем <tex>A(1, 6) = 5</tex> и <tex>A(0, 6) = 0</tex>. Не равны. Следовательно, <tex>1</tex> предмет входит в набор.
Таким образом, набор состоит из <tex>1, 2, 5</tex> предметов.
Стоимость рюкзака <tex>= 5 + 3 + 6 = 14</tex>
Вес рюкзака <tex>= 6 + 4 + 5 = 15</tex>
== Литература ==
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
