Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. (
Рассмотрим следующую функцию. Пусть 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]), что куда более эффективно, чем «наивное» решение.
