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

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

    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;
        }
    }

    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) памяти.

Вариации на тему задачи о сумме подмножеств

Какой максимальный вес не больше заданного можно набрать

Решаем задачу о сумме подмножеств, ищем самое правое true в последней строке таблицы.

int 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 - 1][weight - currentItemWeight])
                canMake[items][weight] = true;
        }
    }

    while (!canMake[items.size()][targetWeight])
       targetWeight--;
    return targetWeight;
}

Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.

Можно ли разделить предметы на два набора одинакового веса

Решаем задачу о сумме подмножеств для targetWeight == (сумма весов предметов) / 2.

bool solve(const vector<int> &itemWeight) {
    vector<vector<bool>> canMake(itemWeight.size() + 1, vector<int>(targetWeight + 1));

    int targetWeight = 0;
    for (int weight : itemWeight)
        targetWeight += weight;
    targetWeight /= 2;

    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;
        }
    }

    return canMake[items.size()][targetWeight];
}

Временная сложность решения Θ(NM). Для таблицы требуется Θ(NM) или Θ(M) памяти.

Also

Можно ли монетами coins набрать сумму targetSum?

Есть лишь одна монета каждого вида		Монет каждого вида неограниченно много
bool solve(const vector<int> &coins, int targetSum) { vector<bool> can(targetSum + 1); can[0] = true; for (int coin : coins) for (int sum = targetSum; sum >= coin; sum--) can[sum] |= can[sum - coin]; return can[targetSum]; }		bool solve(const vector<int> &coins, int targetSum) { vector<bool> can(targetSum + 1); can[0] = true; for (int coin : coins) for (int sum = coin; sum <= targetSum; sum++) can[sum] |= can[sum - coin]; return can[targetSum]; }

Каким минимальными количеством монет coins можно набрать сумму targetSum?

Есть лишь одна монета каждого вида		Монет каждого вида неограниченно много
int solve(const vector<int> &coins, int targetSum) { vector<int> minCoins(targetSum + 1, 1e9); minCoins[0] = 0; for (int coin : coins) for (int sum = targetSum; sum >= coin; sum--) minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1); return minCoins[targetSum] != 1e9 ? minCoins[targetSum] : -1; }		int solve(const vector<int> &coins, int targetSum) { vector<int> minCoins(targetSum + 1, 1e9); minCoins[0] = 0; for (int coin : coins) for (int sum = coin; sum <= targetSum; sum++) minCoins[sum] = min(minCoins[sum], minCoins[sum - coin] + 1); return minCoins[targetSum] != 1e9 ? minCoins[targetSum] : -1; }

Сколько есть способов монетами coins набрать сумму targetSum? Способы, отличающиеся только порядком монет, считаются одинаковыми.

Есть лишь одна монета каждого вида		Монет каждого вида неограниченно много
long long solve(const vector<int> &coins, int targetSum) { vector<long long> ways(targetSum + 1); ways[0] = 1; for (int coin : coins) for (int sum = targetSum; sum >= coin; sum--) ways[sum] += ways[sum - coin]; cout << ways[targetSum]; }		long long solve(const vector<int> &coins, int targetSum) { vector<long long> ways(targetSum + 1); ways[0] = 1; for (int coin : coins) for (int sum = coin; sum <= targetSum; sum++) ways[sum] += ways[sum - coin]; cout << ways[targetSum]; }

Сколько есть способов монетами coins набрать сумму targetSum? Способы, отличающиеся только порядком монет, считаются различными.

Есть лишь одна монета каждого вида		Монет каждого вида неограниченно много
		long long solve(const vector<int> &coins, int targetSum) { vector<long long> ways(targetSum + 1); ways[0] = 1; for (int sum = 1; sum <= targetSum; sum++) for (int coin : coins) if (coin <= sum) ways[sum] += [sum - coin]; cout << ways[targetSum]; }

Ссылки

• algorithmica.org — Задача о рюкзаке, НВП и НОП
• brilliant.org — Backpack Problem