В предыдущих уроках вы решали задачи на числа Фибоначчи и счётные задачи — там рекуррентность была очевидна и одномерна. Задача о рюкзаке — первая в этом блоке двумерная DP: состояние зависит от двух параметров, и именно здесь видно, что «написать рекуррентное соотношение» это главный навык. Постановка задачи**

Есть n предметов. Каждый предмет i имеет вес weights[i] и ценность values[i]. Есть рюкзак грузоподъёмностью W. Нужно выбрать подмножество предметов с максимальной суммарной ценностью, при условии что суммарный вес не превышает W. Каждый предмет либо берём (1), либо не берём (0) — отсюда название 0/1 knapsack.

Почему полный перебор не работает? Для n предметов существует 2ⁿ подмножеств. При n = 30 это больше миллиарда вариантов. При n = 50 — больше квадриллиона. Даже если проверять миллиард вариантов в секунду, n = 60 займёт 1100 лет.

Разберём на конкретном примере. Пять предметов с весами [2, 3, 4, 5, 1] и ценностями [3, 4, 5, 6, 1], грузоподъёмность W = 8. Оптимальный ответ: взять предметы с весами 3 и 4 (индексы 1 и 2) — суммарная ценность 9. Или взять предметы с весами 2, 5, 1 (индексы 0, 3, 4) — ценность 10. Проверить все 32 варианта вручную ещё реально, но при n = 50 — нет. DP-решение: двумерная таблица**

Определим подзадачу. Пусть dp[i][w] — максимальная ценность, которую можно набрать, рассматривая первые i предметов (индексы 0..i-1) при ограничении на вес w.

Рекуррентное соотношение. Стоя перед предметом i (индекс i-1 в нулевой индексации), у нас два варианта:

1. Не берём предмет i: dp[i][w] = dp[i-1][w] — максимум без этого предмета не меняется.

2. Берём предмет i (только если его вес не превышает w): dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1] — берём лучший результат без него, но с освобождённым местом, плюс его ценность.

Итоговый переход: dp[i][w] = max(вариант 1, вариант 2).

Базовые случаи: dp[0][w] = 0 для всех w (ноль предметов — ноль ценности), dp[i][0] = 0 для всех i (нулевая грузоподъёмность — ноль ценности).

static int Knapsack01(int[] weights, int[] values, int W)
{
    int n = weights.Length;
    // dp[i][w] = макс. ценность из первых i предметов при грузоподъёмности w
    int[,] dp = new int[n + 1, W + 1];

    // Базовые случаи: dp[0][*] = 0, dp[*][0] = 0 — уже выставлены по умолчанию

    for (int i = 1; i <= n; i++)
    {
        int wi = weights[i - 1]; // вес i-го предмета (0-индексация)
        int vi = values[i - 1];  // ценность i-го предмета

        for (int w = 0; w <= W; w++)
        {
            // Вариант 1: не берём предмет i
            dp[i, w] = dp[i - 1, w];

            // Вариант 2: берём предмет i (если помещается)
            if (wi <= w)
                dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - wi] + vi);
        }
    }

    return dp[n, W]; // ответ — правый нижний угол таблицы
}

int[] weights = { 2, 3, 4, 5, 1 };
int[] values  = { 3, 4, 5, 6, 1 };
int W = 8;

Console.WriteLine(Knapsack01(weights, values, W)); // 10

Сложность: O(n·W) по времени и O(n·W) по памяти. При n = 1000 и W = 1000 это миллион ячеек — приемлемо. Именно поэтому задача называется NP-hard, но решается псевдополиномиально: сложность полиномиальна по n и W, но W может быть экспоненциальным по числу бит в его записи. На практике W ≤ 10⁶ уже комфортно решается.

Оптимизация памяти: одномерный массив

В двумерной таблице строка i зависит только от строки i-1. Значит, можно хранить только одну строку и обновлять её на месте — при одном условии: обновлять нужно справа налево, чтобы не использовать уже обновлённые значения текущей итерации вместо предыдущей.

static int Knapsack01Optimized(int[] weights, int[] values, int W)
{
    int n = weights.Length;
    int[] dp = new int[W + 1]; // dp[w] = макс. ценность при грузоподъёмности w

    for (int i = 0; i < n; i++)
    {
        int wi = weights[i];
        int vi = values[i];

        // Идём СПРАВА НАЛЕВО — иначе предмет i может быть взят несколько раз
        for (int w = W; w >= wi; w--)
            dp[w] = Math.Max(dp[w], dp[w - wi] + vi);
        // dp[w - wi] здесь — ещё не обновлённое значение (из строки i-1)
    }

    return dp[W];
}

Console.WriteLine(Knapsack01Optimized(weights, values, W)); // 10

Почему справа налево? Если идти слева направо, то при обработке предмета i обновление dp[w] уже использует dp[w - wi], которое на этой же итерации уже могло быть обновлено. Это означало бы, что предмет i берётся дважды — переход к задаче «безграничного рюкзака». В задаче 0/1 каждый предмет только один раз, поэтому — справа налево.

Восстановление набора предметов**

Часто нужно не только знать максимальную ценность, но и какие именно предметы её дают. Для восстановления нужна полная двумерная таблица dp. Идём с конца: от dp[n][W] и движемся назад по предметам.

static (int maxValue, List<int> chosen) Knapsack01WithItems(
    int[] weights, int[] values, int W)
{
    int n = weights.Length;
    int[,] dp = new int[n + 1, W + 1];

    // Заполняем таблицу (то же, что раньше)
    for (int i = 1; i <= n; i++)
    {
        int wi = weights[i - 1];
        int vi = values[i - 1];
        for (int w = 0; w <= W; w++)
        {
            dp[i, w] = dp[i - 1, w];
            if (wi <= w)
                dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - wi] + vi);
        }
    }

    // Восстановление набора — идём обратно по таблице
    var chosen = new List<int>();
    int rem = W; // оставшаяся грузоподъёмность

    for (int i = n; i >= 1; i--)
    {
        // Если значение изменилось по сравнению со строкой без предмета i —
        // значит, предмет i был взят
        if (dp[i, rem] != dp[i - 1, rem])
        {
            chosen.Add(i - 1);      // добавляем индекс предмета (0-based)
            rem -= weights[i - 1];  // уменьшаем оставшийся вес
        }
    }

    chosen.Reverse(); // вернём в порядке возрастания индексов
    return (dp[n, W], chosen);
}

var (maxVal, items) = Knapsack01WithItems(weights, values, W);
Console.WriteLine($"Максимальная ценность: {maxVal}"); // 10
Console.WriteLine($"Индексы предметов: {string.Join(", ", items)}"); // 0, 3, 4

Логика восстановления: если dp[i][rem] == dp[i-1][rem], предмет i не взяли (значение не изменилось бы без него). Если dp[i][rem] != dp[i-1][rem], предмет взяли — уменьшаем rem на его вес и переходим к строке i-1 с новым rem. Этот приём называется traceback или backtracking по таблице DP.

Варианты задачи

Безграничный рюкзак (Unbounded Knapsack) — каждый предмет можно брать любое число раз. Рекуррентность меняется минимально: при обновлении dp[w] вместо dp[i-1][w-wi] используем dp[i][w-wi] — уже обновлённое значение текущей строки. В одномерной версии это значит идти слева направо (обратно по сравнению с 0/1 rюkzakom).

static int KnapsackUnbounded(int[] weights, int[] values, int W)
{
    int n = weights.Length;
    int[] dp = new int[W + 1];

    for (int w = 1; w <= W; w++)       // по грузоподъёмности
        for (int i = 0; i < n; i++)    // по предметам
            if (weights[i] <= w)
                dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);

    return dp[W];
}

Дробный рюкзак (Fractional Knapsack) — можно брать дробные части предметов. Эта задача решается жадным алгоритмом за O(n log n): сортируем предметы по удельной ценности (value/weight) по убыванию и берём предметы целиком пока влезают, последний — дробно. DP здесь избыточен.

Разница принципиальна: в дробном рюкзаке оптимально брать предмет с наибольшей удельной ценностью, и жадный алгоритм всегда даёт глобальный оптимум. В 0/1 рюкзаке это не так: взяв самый ценный предмет по удельной ценности, вы можете потратить грузоподъёмность так, что оставшееся место использовать неэффективно. DP учитывает все комбинации.