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

Задача о рюкзаке — дано [math]k[/math] предметов, i-й предмет имеет массу [math] w_i \gt 0[/math] и стоимость [math] p_i \gt 0[/math]. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины [math]W[/math] (вместимость рюкзака), а суммарная стоимость была максимальна.

Формулировка задачи

Дано [math]k[/math] предметов, [math]W[/math] - вместимость рюкзака, [math]w=\{w_{1},w_{2},...,w_{k}\}[/math] — соответствующий ему набор положительных целых весов, [math]p=\{p_{1},p_{2},...,p_{k}\}[/math] — соответствующий ему набор положительных целых стоимостей. Нужно определить набор бинарных величин [math]B=\{b_{1},b_{2},...,b_{k}\}[/math], где [math]b_{i} = 1 [/math], если предмет включен в набор, [math] b_{i} = 0 [/math], если предмет не включен, такой что:

1. [math]b_{1} w_{1}+ ... + b_{k} w_{k} \le W[/math]

2. [math]b_{1} p_{1}+ ... + b_{k} k_{k} [/math] максимальна.

Алгоритм

Задачу о рюкзаке можно решить несколькими способами:

1. Перебирая все подмножества набора из k предметов. Сложность такого решения [math]O({2^{k}})[/math].

2. Методом Meet-in-the-middle. Сложность решения [math] O({2^{N/2}}\times{N}) [/math]

3. Метод динамического программирование. Сложность - [math]O(k \times W)[/math]. Рассмотрим этот алгоритм подробнее.

Алгоритм [math]O(k \times W)[/math]

Пусть [math]A(s, n)[/math] есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости n, если можно использовать только первые s предметов из заданных k.

[math]A(s, 0) = 0[/math]

[math]A(0, n) = 0[/math]

Найдем [math]A(s, n)[/math]. Возможны 2 варианта:

1. Если предмет [math]s[/math] не попал в рюкзак. Тогда [math]A(s, n) = A(s-1, n)[/math]

2. Если [math]s[/math] попал в рюкзак. Тогда [math]A(s, n) = A(s-1, n-w_{s}) + p_{s}[/math]

Таким образом: [math]A(s,n) = max(A(s-1,n), A(s-1,n-w_{s}) + p_{s})[/math]

Теперь найдем набор предметов, входящих в рюкзак.

Рассмотрим входит ли [math]k[/math] - последний предмет в рюкзак. Если [math]A(k, W)[/math] равно [math]A(k-1, W)[/math], значит последний предмет не входит в набор, иначе входит. Так рекусривно идем до первого предмета. Получаем искомый набор.

Сложность алгоритма [math]O(kW)[/math]

Реализация

Сначала генерируем [math]А[/math]

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]             {иначе, не кладем}

Затем найдем набор [math]ans[/math] предметов, входящих в рюкзак, рекурсивной функцией:

void findAns(s, n)
  if A[s][n] == 0 
    return
  if A[s-1][n] == A[s][n]
    findAns(s-1, n)
  else 
    findAns(s-1, n - w[s]);
    ans.push(s);

Пример

[math]W = 15, k = 5[/math]

[math]w_{1} = 6, p_{1} = 5 [/math]

[math]w_{2} = 4, p_{2} = 3 [/math]

[math]w_{3} = 3, p_{3} = 1 [/math]

[math]w_{4} = 2, p_{4} = 3 [/math]

[math]w_{5} = 5, p_{5} = 6 [/math]

	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 в первой строчке обозначают вместимость рюкзака.

Рассмотрим стоку [math]s = 1[/math]. То есть можно использовать только первый предмет, у которого

[math]w_1 = 6, p_1 = 5[/math].

[math]A(1,n) = 0[/math] при [math]n \le 5[/math],

[math]A(1,n) = 5[/math] при [math] n \ge 6 [/math], так как [math]w_1 \le n[/math]

Рассмотрим строку [math]s=2[/math]. То есть можно использовать первые 2 предмета.

[math]w_1 = 6, p_1 = 5[/math]

[math]w_2 = 4, p_2 = 3[/math]

[math]A(2, n) = A(1,n)[/math], при [math]n \le 3[/math], так как нельзя положить в рюкзак [math]2[/math] предмет.

[math]A(2,n) = max(A(1,n), A(1,n-w_{2}) + p_{2})[/math], при остальных [math]n[/math]. А именно:

[math]A(2,4) = max(0, 0 + 3) = 3[/math]

[math]A(2,5) = max(0, 0 + 3) = 3[/math]

[math]A(2,6) = max(5, 0 + 3) = 5[/math]

[math]A(2,7) = max(5, 0 + 3) = 5[/math]

[math]A(2,8) = max(5, 0 + 3) = 5[/math]

[math]A(2,9) = max(5, 0 + 3) = 5[/math]

[math]A(2,10) = max(5, 5 + 3) = 8[/math]

[math]A(2,11) = max(5, 5 + 3) = 8[/math]

[math] ... [/math]

Максимальная стоимость рюкзака находится в [math]A(5, 15)[/math].

Теперь восстановим набор предметов, из которых состоит максимально дорогой рюкзак.

Сравниваем [math]A(5, 15) = 14[/math] и [math]A(4, 15) = 12[/math]. Не равны. Следовательно, [math]5[/math] предмет входит в искомый набор, переходим к [math]4[/math] предмету с весом рюкзака [math]W - w_5[/math]. То есть [math]15 - 5 = 10[/math]

Сравниваем [math]A(4, 10) = 8[/math] и [math]A(3, 10) = 8[/math]. Равны. Следовательно, [math]4[/math] предмет не входит в набор, переходим к [math]3[/math] предмету с тем же весом рюкзака.

Сравниваем [math]A(3, 10) = 8[/math] и [math]A(2, 10) = 8[/math]. Равны. Следовательно, [math]4[/math] предмет не входит в набор, переходим к [math]2[/math] предмету с тем же весом рюкзака.

Сравниваем [math]A(2, 10) = 2[/math] и [math]A(1, 10) = 5[/math]. Не равны. Следовательно, [math]2[/math] предмет входит в набор, уменьшаем вес рюкзака на [math]w_2[/math], переходим к [math]1[/math] предмету.

Сравниваем [math]A(1, 6) = 5[/math] и [math]A(0, 6) = 0[/math]. Не равны. Следовательно, [math]1[/math] предмет входит в набор.

Таким образом, набор состоит из [math]1, 2, 5[/math] предметов.

Стоимость рюкзака [math]= 5 + 3 + 6 = 14[/math]

Вес рюкзака [math]= 6 + 4 + 5 = 15[/math]

Литература

• Дистанционная подготовка по информатике