Рассмотрим следующую задачу. Имеется некоторое количество предметов обладающих весом и стоимостью. Нужно сделать из них выборку, так чтобы сумма не превышала некоторого порогового значения а суммарная стоимость была максимальна (минимальна). Различают следующие основные разновидности этой задачи:
- 0-1 knapsaсk - каждый предмет мы можем брать не более одного раза
- unbounded knapsack - можно взять неограниченное количество каждого предмета
- bounded knapsack - максимальное количество каждого предмета ограниченно сверху
Данную задачу можно решить с помощью динамического программирования. Для решения всех трех поздачач используются двухмерная таблица. Элемента таблицы в i-ой строке и j-ом столбце это максимальная сумма которую можно набрать используя первые i предметов так чтобы суммарные вес предметов в наборе был равен j.
0-1 Knapsack
Для решения нам необязательно хранить всю таблицу. Достаточно хранить текущую строку и обновлять ее для каждого нового предмета. При добавлении нового предмета для каждого веса от 0 до W мы можем либо использовать этот предмет, либо обойтись только предыдущими в зависимости от полученной стоимости. Веса нужно просматривать в порядке убывания чтобы при просмотре сохраненного значения с меньшим весом мы использовали значение без учета нового предмета.
vector<int> O1_knapsack(vector<Item> &A, int W)
{
int n = sz(A);
vector<int> dp = vector<int>(W + 1, -INF);
dp[0] = 0;
for (int k = 1; k <= n; ++k) {
int wk = A[k - 1].w; // вес
int ck = A[k - 1].c; // стоимость
for (int w = W; w >= wk; --w) {
if (dp[w - wk] != -INF) {
dp[w] = max(dp[w], dp[w - wk] + ck);
}
}
}
return dp;
}
Unbounded knapsack
Задача решается аналогично предыдущей с тем лишь исключением, что теперь веса просматриваются в порядке возрастания, т.к. количество предметов каждого типа неограниченно и обращаясь к меньшему весу мы получаем значение, которое теоретическу уже может включать в себя текущий предмет.
vector<int> unbounded_knapsack(vector<Item> &A, int W)
{
int n = sz(A);
vector<int> dp = vector<int>(W + 1, -INF);
dp[0] = 0;
for (int k = 1; k <= n; ++k) {
int wk = A[k - 1].w; // вес
int ck = A[k - 1].c; // стоимость
for (int w = wk; w <= W; ++w) {
if (dp[w - wk] != -INF) {
dp[w] = max(dp[w], dp[w - wk] + ck);
}
}
}
return dp;
}
Bounded knapsack
Данную задачу можно свести к 0-1 knapsack добавив необходимое количество копий каждого предмета. Однако это существенно увеличивает сложность при больших значениях ограничений на количество предмета - O(NWU), где U - максимум среди ограничений. Можно улучшить эту оценку до O(NWlogU) добавив для каждого предмета веса по степеням двойки. Это даст возможность набрать любой вес от 0 до Wk*Uk. При этом количество весов будет log(Uk). Например если у нас есть Wk=1 и Uk=20 то мы получим веса 1,2,4,8,5 и это даст нам возможность представить любой вес от 1 до 20.
Однако, существует способ решить эту задачу как и предыдущие рассмотренные за время O(NW). Заметим, что
dp[k][w] это минимум среди:
dp[k - 1][w - 0 * wk] + 0 * ck
dp[k - 1][w - 1 * wk] + 1 * ck
dp[k - 1][w - 2 * wk] + 2 * ck
....
dp[k - 1][w - uk * wk] + uk * ck
Мы можем разбить все веса от 0 до W на группы по остатку от деления веса на wk и в пределах каждой группы мы должны быстро считать максимум в окне из (uk + 1) элементов из массива dp[k - 1] с некоторым добавочным значением.
Иными словами имеем следующую задачу. У нас есть массив A из N элементов, необходимо рассчитать максимум для каждого окна размера K, где элемент окна на позиции i равен A[shift+i] + X*i, где shift - смещение окна, X - некоторая константа. Задача поиска минимума в окне массива решается стандартно с использованием
алгоритма поиска максимума в очереди. В данном случае необходима неболшая модификация. Добавим к i-ому элементу массива A величину i*X. Тогда, когда мы будем получать очередной максимум для окна со сдвигом shift мы будем получать максимум для элементов:
A[shift] + shift*X,
A[shift+1] + (shift+1)*X,
...
A[shift+K-1] + (shift+K-1)*X.
Т.е. чтобы получать интересующий нас максимум мы должны из полученного значения вычесть shift*X. Адаптировав это для решения поставленной задачи можно получить следующий код:
Queue q;
vector<int> bounded_knapsack(vector<Item> &A, int W)
{
int n = sz(A);
vector<vector<int>> dp = vector<vector<int>>(2, vector<int>(W + 1, INF));
dp[0][0] = 0;
int prev = 0, cur = 1;
for (int k = 1; k <= n; ++k) {
int wk = A[k - 1].w; // вес
int ck = A[k - 1].c; // стоимость
int uk = A[k - 1].u; // максимальное количество
for (int sw = 0; sw < wk && sw <= W; ++sw) {
q.clear();
int cum = 0;
for (int w = sw; w <= W; w += wk, cum += ck) {
if (dp[prev][w] == INF) {
q.push(INF);
} else {
q.push(dp[prev][w] - cum);
}
while (q.size() > uk + 1) q.pop();
dp[cur][w] = q.get();
if (dp[cur][w] != INF) {
dp[cur][w] += cum;
}
}
}
swap(prev, cur);
}
return dp[prev];
}
Задачи:
