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

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

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

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

1. [math]b_{1} w_{1}+ ... + b_{N} w_{N} \le W[/math]
2. [math]b_{1} p_{1}+ ... + b_{N} p_{N} [/math] максимальна.

Варианты решения

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

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

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

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

Метод динамического программирования

Пусть [math]A(k, s)[/math] есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости [math]s[/math], если можно использовать только первые [math]k[/math] предметов, то есть [math]\{n_1,n_2,...,n_k\}[/math], назовем этот набор допустимых предметов для [math]A(k,s)[/math].

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

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

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

1. Если предмет [math]k[/math] не попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов [math]\{n_1,n_2,...,n_{k-1}\}[/math], то есть [math]A(k,s) = A(k-1, s)[/math]
2. Если [math]k[/math] попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака, где вес [math]s\lt tex\gt уменьшаем на вес \lt tex\gt k[/math]-ого предмета и набор допустимых предметов [math]\{n_1,n_2,...,n_{k-1}\}[/math] плюс стоимость [math]k[/math], то есть [math]A(k-1, s-w_k) + p_k[/math]

Если короче:

1. [math]A(k,s) = A(k-1, s)[/math]
2. [math]A(k,s) = A(k-1, s-w_k) + p_k[/math]

Выберем из этих двух значений максимальное:

[math]A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})[/math]

Стоимость искомого набора равна [math]A(N,W)[/math], так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака [math]W[/math].

Восстановим набор предметов, входящих в рюкзак

Реализация

Сначала генерируем [math]A[/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] предметов, входящих в рюкзак, рекурсивной функцией:

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]O(kW)[/math]

Пример

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

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

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

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

[math]w_{4} = 8, p_{4} = 7 [/math]

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

	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 = 1	0	0	0	1	1	1	1	1	1	1	1	1	1	1
s = 2	0	0	0	1	6	6	6	7	7	7	7	7	7	7
s = 3	0	0	0	1	6	6	6	7	7	10	10	10	11	11
s = 4	0	0	0	1	6	6	6	7	7	10	10	10	13	13
s = 5	0	0	0	1	6	6	6	7	7	10	10	10	13	13

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака [math]n \ge 3[/math], добавляем в рюкзак 1 предмет.

Рассмотрим [math]s = 3[/math], при каждом [math]n \ge 5 ([/math]так как [math]w_3 = 5)[/math] сравниваем [math]A[s-1][n] и A[s-1][n-w_3]+p_3[/math] и записываем в [math]A[s][n][/math] стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимость третьего предмета плюс стоимость рюкзака с вместимостью на [math]w_3[/math] меньше.

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

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

Будем начиная с ячейки, соответствующей ответу, то есть вместимость [math] = W[/math], и можно использовать для составления набора все предметы, определять, входит последний предмет в набор или нет. Для этого сравниваем значение в рассматриваемой ячейке с:

1. Со значением в ячейке с такой же вместимостью, и можно использовать все предметы имеющие

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

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

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

Литература

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