Задача о Рюкзаке (0/1)0/1 Knapsack

Пусть dp[i][w] — наилучшая суммарная ценность, достижимая при выборе из первых i предметов с ограничением по весу w. Для i-го предмета (вес wt, ценность val) есть ровно два варианта: не брать его — тогда dp[i][w] = dp[i-1][w] (задача сводится к первым i-1 предметам с тем же w); или взять его, если он помещается (wt ≤ w) — тогда остаётся вместимость w-wt под первые i-1 предметов, и суммарная ценность dp[i-1][w-wt] + val. Раз оба варианта допустимы (когда предмет помещается), берём максимум: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val). Если предмет не помещается (wt > w), доступен только первый вариант. Базовый случай dp[0][w] = 0 для любого w (нет предметов — нет ценности). Ответ на всю задачу — dp[n][W].Let dp[i][w] be the best total value achievable when choosing among the first i items under a weight limit w. For item i (weight wt, value val) there are exactly two options: skip it — then dp[i][w] = dp[i-1][w] (the problem reduces to the first i-1 items with the same w); or take it, if it fits (wt ≤ w) — leaving capacity w-wt for the first i-1 items, with total value dp[i-1][w-wt] + val. Since both options are valid whenever the item fits, take the max: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val). If the item doesn't fit (wt > w), only the first option is available. The base case is dp[0][w] = 0 for any w (no items, no value). The answer to the whole problem is dp[n][W].

Заполнение таблицы идёт строка за строкой (по i от 1 до n), в каждой строке — по столбцам (по w от 0 до W); каждая ячейка использует только значения из предыдущей строки, поэтому порядок обхода внутри строки не важен для корректности 2D-версии. Восстановление набора выбранных предметов — обратный проход от dp[n][W]: если dp[i][w] == dp[i-1][w], предмет i не был взят, переходим к dp[i-1][w]; иначе он был взят — добавляем его в ответ и переходим к dp[i-1][w-wt].The table is filled row by row (i from 1 to n), and within each row, column by column (w from 0 to W); each cell only uses values from the previous row, so the traversal order within a row doesn't matter for the 2D version's correctness. Reconstructing the chosen items is a backward pass from dp[n][W]: if dp[i][w] == dp[i-1][w], item i wasn't taken — move to dp[i-1][w]; otherwise it was taken — add it to the answer and move to dp[i-1][w-wt].

Практическое замечание об экономии памяти: поскольку строка i использует только строку i-1, всю 2D-таблицу можно сжать в один 1D-массив dp[w] размера W+1, обновляемый на месте. Критично, что при этом столбец w нужно обходить по убыванию (от W до 0): если бы обход шёл по возрастанию, dp[w-wt] уже был бы перезаписан значением ТЕКУЩЕЙ строки i (то есть предмет i уже был бы учтён в нём), и получилась бы задача, где предмет можно брать несколько раз — тот самый неограниченный вариант, разобранный в 2.4.2.4. Обход по убыванию гарантирует, что dp[w-wt] на момент чтения всё ещё хранит значение строки i-1.A practical note on saving memory: since row i only uses row i-1, the entire 2D table can be compressed into a single 1D array dp[w] of size W+1, updated in place. Critically, the w column must then be traversed in decreasing order (from W down to 0): if the traversal went in increasing order, dp[w-wt] would already have been overwritten with a value from the CURRENT row i (meaning item i would already be accounted for in it), and the result would be a problem where an item can be taken multiple times — exactly the unbounded variant covered in 2.4.2.4. Traversing in decreasing order guarantees dp[w-wt] still holds row i-1's value at the time it's read.

int knapsack01(std::vector<int>& wt, std::vector<int>& val, int W) {
    int n = wt.size();
    std::vector<int> dp(W + 1, 0);        // 1D-сжатие, dp[w] = строка i-1 до обновления// 1D compression, dp[w] = row i-1 before the update
    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)      // по убыванию — критично для 0/1// decreasing — critical for 0/1
            dp[w] = std::max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}

Небольшой набор предметов и вместимость W — демонстрация проигрывает заполнение полной 2D-таблицы dp[i][w] строка за строкой, слева направо, а затем восстанавливает выбранные предметы обратным проходом от dp[n][W].A small set of items and a capacity W — the demo auto-plays filling the full 2D table dp[i][w] row by row, left to right, then reconstructs the chosen items with a backward pass from dp[n][W].