- 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]; }
Задачи:
No comments:
Post a Comment