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

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