Теоретический материал: Задача о рюкзаке

Теоретический материал

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

Грабитель, проникший в банк, обнаружил в сейфе k золотых слитков, массами w₁, w₂, ..., w_k килограмм. При этом грабитель может унести не более W килограмм. Определите набор слитков, который должен взять грабитель, чтобы унести как можно больше золота.

Эта задача является частным случаем задачи об укладке рюкзака. Сформулируем ее в общем случае.

Дано k предметов, i-й предмет имеет массу w_i > 0 и стоимость p_i > 0. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W (вместимость рюкзака), а суммарная стоимость была максимальна. Другими словами, нужно определить набор бинарных величин (b₁, b₂,..., b_k), такой, что

b₁w₁ + b₂w₂ +...+ b_kw_k $\displaystyle \le$ W,

а величина b₁p₁ + b₂p₂ +...+ b_kp_k -- максимальная. Величина b_i равна 1, если i-й предмет включается в набор, и равна 0 в противном случае.

Задача укладки рюкзака очень сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O(2^k). В настоящее время неизвестен (и, скорее всего, вообще не существует) алгоритм решения этой задачи, сложность которого является многочленом от k.

Мы рассмотрим решение данной задачи для случая, когда все входные данные -- целочисленные, сложность которого будет O(kW).

Рассмотрим следующую функцию. Пусть A(s, n) есть максимальная стоимости предметов, которые можно уложить в рюкзак максимальной вместимости n, если можно использовать только первые s предметов из заданных k.

Зададим краевые значения функции A(s, n).

Если s = 0, то A(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0).

Если n = 0, то A(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).

Теперь составим рекуррентное соотношение в общем случае. Необходимо из предметов с номерами 1, ..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак.

Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1, ..., s - 1, следовательно, A(s, n) = A(s - 1, n).

Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - w_s, а от добавления предмета s общая стоимость рюкзака увеличивается на p_s. Значит, A(s, n) = A(s - 1, n - w_s) + p_s. Теперь из двух возможных вариантов составить рюкзак массы, не превосходящей n, из предметов 1, ..., s нужно выбрать наилучший:

A(s, n) = max $\displaystyle \left(\vphantom{A(s-1,n),A(s-1,n-w_s)+p_s}\right.$ A(s - 1, n), A(s - 1, n - w_s) + p_s $\displaystyle \left.\vphantom{A(s-1,n),A(s-1,n-w_s)+p_s}\right)$ .

Теперь составим программу. Будем считать, что веса предметов хранятся в массиве w[1], ..., w[k], а их стоимости в массиве p[1], ..., p[k]. Значения функции A(s, n), где 0 $\le$ s $\le$ k, 0 $\le$ n $\le$ W, будем хранить в массиве A[k+1][W+1].

int A[k+1][W+1];
for(n=0;n<=W;++n)       // Заполняем нулевую строчку
    A[0][n]=0;
for(s=1;s<=k;++s)       // s - максимальный номер предмета, 
{                       // который можно использовать
    for(n=0;n<=W;++n)   // n - вместимости рюкзака
    {
        A[s][n]=A[s-1][n]; 
        if ( n>=w[s] && ( A[s-1][n-w[s]]+p[s] > A[s][n]) )
            A[s][n] = A[s-1][n-w[s]]+p[s];
    }
}

В результате исполнения такого алгоритма в элементе массива A[k][W] будет записан ответ на поставленную задачу. Легко видеть, что сложность этого алгоритма, равно как и объем используемой им памяти, являются величиной O(kW).

Рассмотрим пример работы этого алгоритма. Пусть максимальная вместимость рюкзака W = 15, количество предметов k = 5, их стоимости и массы таковы:
w₁ = 6, p₁ = 5, w₂ = 4, p₂ = 3, w₃ = 3, p₃ = 1,
w₄ = 2, p₄ = 3, w₅ = 5, p₅ = 6.

В приведенной ниже таблице указаны значения заполненного массива A[k+1][W+1].

	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
s = 1	0	0	0	0	0	5	5	5	5	5	5	5	5	5	5
s = 2	0	0	0	3	3	5	5	5	5	8	8	8	8	8	8
s = 3	0	0	1	3	3	5	5	5	6	8	8	8	9	9	9
s = 4	0	3	3	3	4	6	6	8	8	8	9	11	11	11	12
s = 5	0	3	3	3	6	6	9	9	9	10	12	12	14	14	14

Первая строка массива соответствует значениям A(0, n). Поскольку ни одного предмета брать нельзя, то строка заполнена нулями: из пустого множества предметов можно составить рюкзак нулевой массы.

Вторая строка массива соответствует значению s = 1, то есть рюкзак можно составлять только из первого предмета. Вес этого предмета w₁ = 6, а его стоимость p₁ = 5. Поэтому при n < 6 мы не можем включить этот предмет в рюкзак и значение A(1, n) равно 0 при n < 6. Если n $\ge$ w₁, то мы можем включить первый предмет в рюкзак, а поскольку других предметов нет, то A(1, n) = 5 (так как p₁ = 5).

Рассмотрим третью строку массива, соответствующую двум предметам (s = 2). Добавляется второй предмет, более легкий и менее ценный, чем первый (w₂ = 4, p₂ = 3). Поэтому A(2, n) = 0 при n < 4 (ни один предмет взять нельзя), A(2, n) = 3 при n = 4 и n = 5 (в рюкзак включается предмет номер 2 ценности 3), A(2, n) = 5 при 6 $\le$ n $\le$ 9 (при данном n выгоднее в рюкзак включить предмет 1, поскольку его ценность выше) и, наконец, A(2, n) = 8 при n $\ge$ 10 (при данной вместимости рюкзака можно взять оба предмета).

Аналогично заполняются остальные строки массива, при заполнении элемента A(s, n) рассматривается две возможности: включать или не включать предмет с номером s.

Как теперь вывести на экран тот набор предметов, который входит в максимальный рюкзак? Сравним значение A[k][W] со значением A[k-1][W]. Если они равны, то максимальный рюкзак можно составить без использования предмета с номером k. Если не равны, то предмет c номером k обязательно входит в максимальный рюкзак. В любом случае, задача печати рюкзака сводится к задаче печати рюкзака для меньшего числа предметов. Напишем это в виде рекурсивной функции Print(int s, int n), которая по параметрам s и n печатает номера предметов, входящих в максимальный рюкзак массой не более n и составленный из предметов 1, ..., s:

void Print(int s, int n)
{
  if (A[s][n]==0) // максимальный рюкзак для параметров (s,n)
    return;        // имеет нулевую ценность, 
                   // поэтому ничего не выводим
  else if (A[s-1][n] == A[s][n]) 
    Print(s-1,n);  // можно составить рюкзак без предмета s
  else
  {                               
    Print(s-1,n-w[s]); // Предмет s должен обязательно 
    cout<<s<<endl;     // войти в рюкзак
  }
}

Для печати искомого рюкзака необходимо вызвать функцию с параметрами (k,W).

В приведенном примере для печати максимального рюкзака вызовем функцию Print(5,15). Поскольку A(5, 15) = 14, а A(4, 15) = 12 (с использованием только первых 4 предметов мы можем собрать рюкзак максимальной стоимости 12, а с использованием всех 5 предметов -- стоимости 14), предмет номер 5 обязательно входит в рюкзак. Далее рассмотрим A(4, 10) (общая вместимость рюкзака уменьшилась на вес включенного предмета). Поскольку A(4, 10) = A(3, 10) = A(2, 10) = 8, то мы можем исключить из рассмотрения предметы номер 4 и 3 -- можно собрать рюкзак вместимости 10 и стоимости 8 только из первых двух предметов. Для этого необходимо включить оба этих предмета. Таким образом, оптимальный рюкзак будет состоять из предметов 1, 2, 5, его масса будет равна 6 + 4 + 5 = 15, а стоимость -- 5 + 3 + 6 = 14.

Можно составить рюкзак и по-другому. Поскольку вес предмета 4 равен двум, его стоимость p₄ равна трём, а A(4, 10) = A(3, 8) + p₄, то мы можем включить в наш рюкзак предмет 4. Теперь рассмотрим A(3, 8) = 5 -- как составить рюкзак массы не более 8 и стоимости 5 из первых трех предметов. Поскольку A(3, 8) = A(2, 8) = A(1, 8) = 5, то мы исключаем из рассмотрения предметы 3 и 2, но включаем предмет 1. Получим рюкзак из предметов 1, 4, 5, его масса будет 6 + 2 + 5 = 13 и стоимость также равна 5 + 3 + 6 = 14. Поскольку стоимость обоих полученных рюкзаков получилась одинаковой, а масса в каждом случае не превосходит максимально допустимого значения W = 15, то оба решения подходят.