Knapsack problem

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. (Wikipedia)

1. Когда каждый тип предмета можно брать неограниченное количество раз:

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

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

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

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

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

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

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

F(s, n) = max ( F(s - 1, n), F(s - 1, n - ws) + ps ).

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

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

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

Рассмотрим пример работы этого алгоритма. Пусть максимальная вместимость рюкзака W = 15, количество предметов k = 5, их стоимости и массы таковы:
w1 = 6, p1 = 5, w2 = 4, p2 = 3, w3 = 3, p3 = 1,
w4 = 2, p4 = 3, w5 = 5, p5 = 6.

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

2. Когда надо получить не только стоимость, но и сам набор:

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

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

3. Когда каждую вещь можно брать только один раз:

Тут всё ещё проще: надо просто в каждой итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[n-w[s]], там всё ещё будет записано, набор какой максимальной стоимости веса n — w[s] можно получить, используя только вещи 0..s-1. Следовательно, если получится, что в оптимальном наборе надо использовать s-тую вещь, то она будет использована только один раз.

4. Выбор значения, как можно более близкого к данному:

Если нет стоимости, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному.

В всех случаях ассимптотика времени работы и используемой памяти та же.

5. Когда каждую вещь можно брать определённое количество раз:

Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.

Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)

Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.

Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.