297
правок
Изменения
Нет описания правки
'''Задача о рюкзаке''' — дано <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>, если предмет не включен, такой что:
== Варианты решения ==
'''Задачу о рюкзаке можно решить несколькими способами:'''
== Алгоритм <tex>O(k \times W)</tex> ==
Найдем <tex>A(s, n)</tex>. Возможны 2 варианта:
Таким образом:
Рассмотрим входит ли <tex>k</tex> - последний предмет в рюкзак. Если <tex>A(k, W)</tex> равно <tex>A(k-1, W)</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> предметов, входящих в рюкзак, рекурсивной функцией:
if A[s][n] == 0
return
findAns(s-1, n - w[s]);
ans.push(s);
Сложность алгоритма <tex>O(kW)</tex>
== Пример ==
