Задача о рюкзаке и связанные задачи

Задача о сумме подмножеств (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) памяти.