Задача о рюкзаке и связанные задачи
Задача о сумме подмножеств (subset sum problem)
Можно ли набрать заданный вес
Есть несколько предметов, для каждого известен вес. Можем ли мы выбрать несколько предметов так, чтобы общий вес был в точности равен заданному числу?
vector<int> itemWeight; // веса предметов int targetWeight; // вес, который нужно набрать
Будем заполнять таблицу canMake[][]. Строки таблицы соответствуют количеству рассмотренных предметов: нулевая строка — ноль предметов, первая строка — один предмет, ..., N-я строка — N предметов. Столбцы таблицы соответствуют весам от 0 до заданного веса. В ячейках хранятся true и false: canMake[items][weight] == true, если мы можем набрать вес weight, используя некоторые из items первых предметов.
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));
Как должна выглядеть нулевая строка таблицы? В нулевой строке мы описываем ситуацию, когда не рассмотрено ещё ни одного предмета; какие веса мы при этом можем набрать? Очевидно, только вес 0. Поэтому ячейка canMake[0][0] должна содержать true, а остальные ячейки первой строки — false.
суммарные веса 0 1 2 3 4 5 6 7 8 9 10 строка canMake[0] 1 0 0 0 0 0 0 0 0 0 0 (предметов пока нет)
Теперь разберёмся, как должна выглядеть первая строка таблицы (она соответствует первому предмету). Пусть, для определённости, вес первого предмета — 3 (itemWeight[0] == 3). Какие веса мы теперь можем набрать?
Нам всё ещё доступен вес 0 (если мы не будем брать первый предмет), но теперь мы можем получить ещё и вес 3 (если мы возьмём первый предмет).
суммарные веса 0 1 2 3 4 5 6 7 8 9 10 строка canMake[0] 1 0 0 0 0 0 0 0 0 0 0 (предметов пока нет) строка canMake[1] 1 0 0 1 0 0 0 0 0 0 0 (вес предмета — 3)
Далее — вторая строка таблицы (она соответствует первым двум предметам). Пусть вес второго предмета — 5 (itemWeight[1] == 5). Какие веса мы теперь можем набрать?
Нам всё ещё доступны веса 0 и 3 (если мы не будем брать второй предмет), но теперь мы можем получить ещё веса 5 (если мы до этого не брали ничего, а теперь возьмём второй предмет) и 8 (если мы до этого взяли первый предмет и получили вес 3, а сейчас добавим второй предмет).
суммарные веса 0 1 2 3 4 5 6 7 8 9 10 строка canMake[0] 1 0 0 0 0 0 0 0 0 0 0 (предметов пока нет) строка canMake[1] 1 0 0 1 0 0 0 0 0 0 0 (вес предмета — 3) строка canMake[2] 1 0 0 1 0 1 0 0 1 0 0 (вес предмета — 5)
Далее — третья строка таблицы (она соответствует первым трём предметам). Пусть вес третьего предмета — 2 (itemWeight[2] == 2).
Раньше (без третьего предмета) мы могли набрать веса 0, 3, 5 и 8. Теперь (с третьим предметом) можем дополнительно набрать 2, 5, 7 и 10. Обратите внимание, что вес 5 мы могли набрать как без третьего предмета (просто взяв второй предмет с весом 5), так и с ним (взяв первый и третий предметы с весами 3 и 2); ничего необычного в этой ситуации нет.
суммарные веса 0 1 2 3 4 5 6 7 8 9 10 строка canMake[0] 1 0 0 0 0 0 0 0 0 0 0 (предметов пока нет) строка canMake[1] 1 0 0 1 0 0 0 0 0 0 0 (вес предмета — 3) строка canMake[2] 1 0 0 1 0 1 0 0 1 0 0 (вес предмета — 5) строка canMake[3] 1 0 1 1 0 1 0 1 1 0 1 (вес предмета — 2)
Сделаем общие выводы о том, как заполняются строки таблицы. Когда будет true в ячейке canMake[items][weight], то есть когда мы можем набрать вес weight первыми items предметами?
- Во-первых, если мы могли набрать вес weight только предыдущими предметами, не используя новый. То есть, если в предыдущей строке на позиции weight было true (canMake[items - 1][weight] == true).
- Во-вторых, если мы могли набрать вес (weight - currentItemWeight) предыдущими предметами (currentItemWeight — вес текущего предмета). В этом случае, если мы добавим текущий предмет, то мы получим как раз вес weight. То есть, если в предыдущей строке на позиции (weight - currentItemWeight) было true (canMake[items - 1][weight - currentItemWeight] == true).
Теперь мы готовы написать код заполнения таблицы:
bool solve(const vector<int> &itemWeight, int targetWeight) {
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1)); // создаём таблицу, заполненную false
canMake[0][0] = true; // нулём предметов мы можем набрать только вес 0
for (int items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1]; // вес текущего предмета
for (int weight = 0; weight <= targetWeight; weight++) {
if (canMake[items - 1][weight]) // если предыдущими предметами могли набрать вес weight, то и сейчас можем набрать вес weight
canMake[items][weight] = true;
if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight])
canMake[items][weight] = true; // если предыдущими предметами могли набрать вес (weight - currentItemWeight), то сейчас можем набрать вес weight
}
}
return canMake[items.size()][targetWeight];
}
Ответ на задачу в итоге будет записан в последнюю ячейку последней строки (canMake[itemWeight.size()][targetWeight]).
Временная сложность решения — Θ(NM) (N — количество предметов, M — целевой вес). Для таблицы требуется Θ(NM) памяти.
Можно ли набрать заданный вес, каждый предмет можно брать несколько раз
Посмотрим, как изменится заполнение таблицы:
суммарные веса 0 1 2 3 4 5 6 7 8 9 10 строка canMake[0] 1 0 0 0 0 0 0 0 0 0 0 (предметов пока нет) строка canMake[1] 1 0 0 1 0 0 1 0 0 1 0 (вес предмета — 3) строка canMake[2] 1 0 0 1 0 1 1 0 1 1 1 (вес предмета — 5) строка canMake[3] 1 0 1 1 1 1 1 1 1 1 1 (вес предмета — 2)
canMake[items][weight] == true, если canMake[items - 1][weight] == true или canMake[items][weight - currentItemWeight] == true.
bool solve(const vector<int> &itemWeight, int targetWeight) {
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));
canMake[0][0] = true;
for (int items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1];
for (int weight = 0; weight <= targetWeight; weight++) {
if (canMake[items - 1][weight])
canMake[items][weight] = true;
if (weight >= currentItemWeight && canMake[items][weight - currentItemWeight])
canMake[items][weight] = true;
}
}
return canMake[items.size()][targetWeight];
}
Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) памяти.
Заметим, что в данном случае мы можем не делать двумерную таблицу. Нам будет достаточно одной строки canMake[].
bool solve(const vector<int> &itemWeight, int targetWeight) {
vector<bool> canMake(targetWeight + 1);
canMake[0] = true;
for (int items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1];
for (int weight = currentItemWeight; weight <= targetWeight; weight++) {
if (canMake[weight - currentItemWeight])
canMake[weight] = true;
}
}
return canMake[targetWeight];
}
Временная сложность решения Θ(NM). Для таблицы требуется Θ(M) памяти.
Можно ли набрать заданный вес, Θ(M) памяти
Как и в предыдущем случае, мы можем не делать двумерную таблицу. Нам будет достаточно одной строки canMake[].
Здесь, однако, нужно обратить внимание на то, что если мы будем обновлять строку слева направо, то мы будем учитывать один и тот же предмет несколько раз (как в предыдущем случае). То есть, например, если первый предмет имеет вес 3, то мы запишем true в ячейку 3 (так как в ячейке 0 записано true), затем в ячейку 6 (так как в ячейке 3 записано true), затем в ячейку 9 (так как в ячейке 6 записано true)...
Чтобы избежать такой ситуации, следует обновлять строку не слева направо, а справа налево. Тогда в ячейках слева от текущей никогда не будет изменений, связанных с текущим предметом.
bool solve(const vector<int> &itemWeight, int targetWeight) {
vector<bool> canMake(targetWeight + 1);
canMake[0] = true;
for (int items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1];
for (int weight = targetWeight; weight >= currentItemWeight; weight--) {
if (canMake[weight - currentItemWeight])
canMake[weight] = true;
}
}
return canMake[targetWeight];
}
Временная сложность решения Θ(NM). Для таблицы требуется Θ(M) памяти.
Можно ли набрать заданный вес, мало предметов, очень большие веса (⋆)
Мы уже не сможем решить такую задачу при помощи динамического программирования, так как при очень большом targetWeight потребуется очень большая таблица, которая не уместится в память (не говоря уже о времени её заполнения).
Если у нас < 25 предметов, можно просто перебрать все их подмножества (рекурсивно или масками, временная сложность O(2^N)).
Если у нас < 50 предметов, кроме перебора понадобится техника meet in the middle. Разделим предметы на две половины. Для каждой половины сделаем set из всех весов, которые можно составить из предметов в этой половине. Дальше нам нужно найти в двух setах два элемента, в сумме дающие targetWeight.
unordered_set<long long> getTotalWeights(const vector<long long> &itemWeight) {
unordered_set<long long> totalWeights;
for (int mask = 0; mask < (1 << itemWeight.size()); mask++) {
long long totalWeight = 0;
for (int bit = 0; bit < itemWeight.size(); bit++) {
if (mask & (1 << bit))
totalWeight += itemWeight[bit];
}
totalWeights.push_back(totalWeight);
}
return totalMasses;
}
bool solve(const vector<long long> &itemWeight, long long targetWeight) {
auto mid = itemWeight.begin() + itemWeight.size() / 2;
unordered_set<long long> aWeights = getTotalWeights({itemWeight.begin(), mid});
unordered_set<long long> bWeights = getTotalWeights({mid, itemWeight.end()});
for (long long aWeight : aWeights) {
if (bWeights.count(targetWeight - aWeight))
return true;
}
return false;
}
Временная сложность решения Θ(2^(N/2)). Для множеств требуется O(2^(N/2)) памяти.
Номера предметов, дающих заданный вес
Иногда в задаче требуется не только определить, можем ли мы набрать заданный вес, но и вывести сертификат — номера (индексы) предметов, которые мы должны взять.
Вдобавок к таблице canMake[][] сделаем таблицу take[][], в которой будем отмечать, брали ли мы последний предмет. take[items][weight] == true, если, когда мы рассматривали items предметов, мы смогли набрать вес weight, взяв последний предмет (его индекс — (items - 1)).
Заполнение таблицы take[][] происходит одновременно с заполнением таблицы canMake[][]. Всякий раз, когда мы смогли набрать вес при помощи нового предмета, мы ставим true не только в canMake[][], но и в take[][].
if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight]) {
canMake[items][weight] = true;
take[items][weight] = true;
}
Когда у нас есть заполненная таблица take[][], мы можем по ней восстановить номера использованных предметов. Обозначим за weight вес предметов, которые нам нужно взять (изначально weight == targetWeight).
Как понять, взяли ли мы самый последний предмет? Если take[items][weight] == true, то мы его брали, иначе — не брали. Если мы взяли последний предмет, то weight нужно уменьшить на itemWeight[items - 1].
Как понять, взяли ли мы предпоследний предмет? Если take[items - 1][weight] == true, то мы его брали, иначе — не брали. Если мы взяли предпоследний предмет, то weight нужно уменьшить на itemWeight[items - 2].
И так далее, от конца к началу мы определяем, брали или нет мы каждый из предметов, попутно уменьшая weight.
vector<int> solve(const vector<int> &itemWeight, int targetWeight) {
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));
vector<vector<bool>> take(itemWeight.size() + 1, vector<int>(targetWeight + 1));
canMake[0][0] = true;
for (int items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1];
for (int weight = 0; weight <= targetWeight; weight++) {
if (canMake[items - 1][weight])
canMake[items][weight] = true;
if (weight >= currentItemWeight && canMake[items - 1][weight - currentItemWeight]) {
canMake[items][weight] = true;
take[items][weight] = true;
}
}
}
if (!canMake[itemWeight.size()][targetItem])
return {};
vector<int> takenItemIndexes;
for (int items = itemWeight.size(), weight = targetWeight; items > 0; items--) {
if (take[items][weight]) {
takenItemIndexes.push_back(items - 1);
weight -= itemWeight[items - 1];
}
}
return takenItemIndexes;
}
Временная сложность решения Θ(NM). Для таблиц требуется Θ(NM) памяти.
Номера предметов, дающих заданный вес, Θ(M) памяти (⋆)
- stackoverflow.com/questions/51941993/0-1-knapsack-find-solution-set-in-space-optimised-implementation
- www.cs.colostate.edu/~cs575dl/Sp2015/Lectures/Knapsack.pdf
vector<bool> getCanMake(const vector<int> &itemWeight, int targetWeight, int l, int r) {
vector<bool> canMake(targetWeight + 1);
canMake[0] = true;
for (int itemIndex = l; itemIndex <= r; itemIndex++) {
int currentItemWeight = itemWeight[itemIndex];
for (int weight = currentItemWeight; weight <= targetWeight; weight++) {
if (canMake[weight - currentItemWeight])
canMake[weight] = true;
}
}
return canMake;
}
vector<int> solve(const vector<int> &itemWeight, int targetWeight, int l, int r) {
if (l == r)
return targetWeight == itemWeight[l] ? { l } : {};
int m = l + (r - l) / 2;
vector<bool> aCan = getCanMake(itemWeight, targetWeight, l, m);
vector<bool> bCan = getCanMake(itemWeight, targetWeight, m + 1, r);
int aWeight = 0, bWeight = targetWeight;
while (!aCan[aWeight] || !bCan[bWeight]) {
aWeight++;
bWeight--;
}
vector<int> aItemIndexes = solve(itemWeight, aWeight, l, m);
vector<int> bItemIndexes = solve(itemWeight, bWeight, m + 1, r);
aItemIndexes.insert(aItemIndexes.end(), bIntemIndexes.begin(), bItemIndexes.end());
return aItemIndexes;
}
Временная сложность решения Θ(NM). Для таблицы требуется Θ(M) памяти.