7.4 Задачи о рюкзаке¶

Термин «задачи о рюкзаке» объединяет задачи, в которых дан набор объектов, и нужно выбрать некоторое подмножество, удовлетворяющее нужным условиям. Очень часто такие задачи удобно решать с помощью динамического программирования.

В этом разделе рассмотрим такую постановку:

Дан набор весов (w_1, w_2, \dots, w_n). Нужно определить все суммы, которые можно получить, выбирая некоторые из этих весов.

Пример¶

Пусть веса равны:

[ [2,4,4,7] ]

Тогда можно получить такие суммы:

То есть достижимы суммы:

[ 0,2,4,6,7,8,9,10,12,13,14,15,17. ]

Например, сумма (13) получается как (2+4+7), а сумма (15) — как (4+4+7).

Идея динамики¶

Будем рассматривать подзадачи, в которых разрешено использовать только первые (k) весов.

Обозначим:

если сумму (x) можно набрать с помощью первых (k) весов, и

если это невозможно.

Тогда возникает естественный переход:

Почему формула верна¶

Для веса (w_k) есть ровно два варианта:

1. Мы берём этот вес. Тогда осталось проверить, можно ли набрать сумму (x-w_k) первыми (k-1) весами.

2. Мы не берём этот вес. Тогда нужно проверить, достижима ли сумма (x) без него, то есть первыми (k-1) весами.

Если хотя бы один из этих двух вариантов возможен, то сумма (x) достижима.

Базовые случаи¶

Если мы не используем ни одного веса, то можно получить только сумму 0:

Это важная отправная точка для всей динамики.

Таблица состояний¶

Для весов ([2,4,4,7]) таблица истинности будет такой:

После вычисления этой таблицы значение (possible(x,n)) сразу отвечает на вопрос, достижима ли сумма (x) с использованием всех весов.

Решение с двумерной динамикой¶

Пусть (W) — сумма всех весов. Тогда можно построить таблицу DP размера (O(nW)).

possible[0][0] = true;

for (int k = 1; k <= n; k++) {
    for (int x = 0; x <= W; x++) {
        if (x - w[k] >= 0)
            possible[x][k] |= possible[x - w[k]][k - 1];
        possible[x][k] |= possible[x][k - 1];
    }
}

Что здесь происходит¶

• possible[x][k] хранит, можно ли набрать сумму x, используя первые k весов;
• переход «взять текущий вес» реализован строкой possible[x][k] |= possible[x - w[k]][k - 1];
• переход «не брать текущий вес» реализован строкой possible[x][k] |= possible[x][k - 1];

Такое решение наглядное, но использует довольно много памяти.

Оптимизация памяти¶

Можно заметить, что для вычисления очередного слоя по (k) нам нужен только предыдущий слой. Поэтому вместо двумерной таблицы удобно хранить одномерный массив:

[ possible[x] = \text{можно ли набрать сумму } x. ]

Тогда получаем более компактное решение:

possible[0] = true;

for (int k = 1; k <= n; k++) {
    for (int x = W; x >= 0; x--) {
        if (possible[x]) possible[x + w[k]] = true;
    }
}

Почему проход справа налево обязателен¶

Это ключевой момент.

Если бы мы шли по x слева направо, то один и тот же вес можно было бы использовать несколько раз в рамках одной итерации. А нам нужно, чтобы каждый вес использовался не более одного раза.

Именно поэтому массив обновляется справа налево: так новые значения не успевают повлиять на ещё не обработанные состояния текущего шага.

Небольшая иллюстрация¶

Для весов ([2,4,4,7]) одномерная динамика обновляется так:

flowchart TD
    A[Старт: достижима только сумма 0] --> B[Добавляем вес 2]
    B --> C[Появляется сумма 2]
    C --> D[Добавляем вес 4]
    D --> E[Появляются суммы 4 и 6]
    E --> F[Добавляем ещё один вес 4]
    F --> G[Появляются суммы 8 и 10]
    G --> H[Добавляем вес 7]
    H --> I[Получаем новые суммы 7, 9, 13, 15, 17 и другие]

Сложность¶

Двумерная версия¶

• Время: (O(nW))
• Память: (O(nW))

Одномерная версия¶

• Время: (O(nW))
• Память: (O(W))

Здесь (W) — сумма всех весов.

Главное, что стоит запомнить¶

1. Во многих задачах о рюкзаке удобно думать так: что можно получить после обработки первых (k) предметов.
2. Для каждого предмета обычно есть два варианта: взять или не взять.
3. Часто двумерную динамику можно сжать до одномерной.
4. В задаче о достижимых суммах при сжатии памяти нужно обновлять массив справа налево.

Такой подход — одна из базовых моделей динамического программирования и встречается во множестве задач: от проверки достижимости суммы до максимизации ценности при ограничении на вес.