297
правок
Изменения
м
В первой строке как только вместимость рюкзака <tex>n /ge 3</tex>, добавляем в рюкзак 1 предмет.
Во второй строке, когда можно использовать первые <tex>2</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>k</tex> предметов, <tex>i-ыйk_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
== Формулировка задачи ==
* Перебирая все подмножества набора из k предметов. Сложность такого решения <tex>O({2^{k}})</tex>.
* Методом [[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>
* Метод динамического программированиепрограммирования. Сложность - <tex>O(k \times W)</tex>. Рассмотрим этот алгоритм подробнее.
== Алгоритм <tex>O(k \times W)</tex> Метод динамического программирования ==
Пусть <tex>A(s, n)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.
== Реализация ==
Сначала генерируем <tex>АA</tex>.
for i = 0..W
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || 0|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12|| 13
|-
| s = 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0|| 0
| s = 5|| 0|| 0|| 0|| 1|| 6|| 6|| 6|| 7|| 7|| 10|| 10|| 10|| 13|| 13
|}
Числа от 0 до 15 13 в первой строчке обозначают вместимость рюкзака. В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет. Рассмотрим <tex>s = 3</tex>, при каждом <tex>n \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[s-1][n] и A[s-1][n-w_3]+p_3</tex> и записываем в <tex>A[s][n]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимость третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше. Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>. '''Теперь восстановим набор предметов, из которых состоит максимально дорогой рюкзак.'''
Таким образом, набор состоит из <tex>1, 2, 5</tex> предметов.
