Задача о рюкзаке и связанные задачи
Задача о сумме подмножеств (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).
Теперь мы готовы написать код заполнения таблицы:
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1)); // создаём таблицу, заполненную false
canMake[0][0] = true; // нулём предметов мы можем набрать только вес 0
for (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
}
}
Ответ на задачу в итоге будет записан в последнюю ячейку последней строки (canMake[itemWeight.size()][targetWeight]).
Временная сложность решения — O(NM) (N — количество предметов, M — целевой вес). Для таблицы требуется O(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.
vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));
canMake[0][0] = true;
for (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;
}
}
Временная сложность решения O(NM). Для таблицы требуется O(NM) памяти.
Заметим, что в данном случае мы можем не делать двумерную таблицу. Нам будет достаточно одной строки canMake[].
vector<bool> canMake(targetWeight + 1);
canMake[0] = true;
for (items = 1; items <= itemWeight.size(); items++) {
int currentItemWeight = itemWeight[items - 1];
for (int weight = curretItemWeight; weight <= targetWeight; weight++) {
if (canMake[weight - currentItemWeight])
canMake[weight] = true;
}
}
Временная сложность решения O(NM). Для таблицы требуется O(M) памяти.
Задача о сумме подмножеств, O(M) памяти
Как и в предыдущем случае, мы можем не делать двумерную таблицу. Нам будет достаточно одной строки canMake[].
Здесь, однако, нужно обратить внимание на то, что если мы будем обновлять строку слева направо, то мы будем учитывать один и тот же предмет несколько раз (как в предыдущем случае). То есть, например, если первый предмет имеет вес 3, то мы запишем true в ячейку 3 (так как в ячейке 0 записано true), затем в ячейку 6 (так как в ячейке 3 записано true), затем в ячейку 9 (так как в ячейке 6 записано true)...
Чтобы избежать такой ситуации, следует обновлять строку не слева направо, а справа налево. Тогда в ячейках слева от текущей никогда не будет изменений, связанных с текущим предметом.
vector<bool> canMake(targetWeight + 1);
canMake[0] = true;
for (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;
}
}
Временная сложность решения O(NM). Для таблицы требуется O(M) памяти.