kz-maxx

RU KZ
← Главная

Задача о рюкзаке

0/1 Knapsack: рекурсия, мемоизация, итеративный DP и оптимизация памяти

Что такое задача о рюкзаке?

Задача о рюкзаке — это классическая задача динамического программирования.

Есть n предметов. У каждого предмета есть:

  • weight[i] — вес предмета
  • value[i] — ценность предмета

Есть рюкзак вместимостью W. Нужно выбрать некоторые предметы так, чтобы:

общий вес ≤ W
общая ценность была максимальной
В 0/1 knapsack каждый предмет можно взять максимум один раз: либо берем предмет, либо не берем.

Простой пример

Пусть вместимость рюкзака:

W = 5

Предметы:

Предмет Вес Ценность
1 3 10
2 2 7
3 4 12

Лучший выбор:

взять предмет 1 и предмет 2
вес = 3 + 2 = 5
ценность = 10 + 7 = 17

Ответ: 

17

Главная идея

Для каждого предмета у нас есть два варианта:

  • не брать предмет
  • взять предмет, если хватает места
answer = max(
  вариант без предмета,
  вариант с предметом
)

Рекурсивный метод

Сначала удобно думать рекурсивно.

Пусть: 

f(i, w)

Это максимальная ценность, которую можно получить, если мы рассматриваем первые i предметов и у нас осталось место w.

i — сколько предметов рассматриваем
w — текущая вместимость рюкзака

Рекурсивный переход

Рассмотрим предмет i.

Вариант 1: не брать предмет i. 

f(i - 1, w)

Вариант 2: взять предмет i. Это можно сделать только если его вес не больше текущей вместимости. 

f(i - 1, w - weight[i]) + value[i]

Тогда формула: 

f(i, w) = max(f(i - 1, w), f(i - 1, w - weight[i]) + value[i]);

Базовый случай

Если предметов нет, то ценность равна 0. 

if (i == 0) {
    return 0;
}

Еще если вместимость стала 0, больше ничего взять нельзя. 

if (w == 0) {
    return 0;
}

Обычная рекурсия

int solve(int i, int w) {
    if (i == 0 || w == 0) {
        return 0;
    }

    int ans = solve(i - 1, w);

    if (weight[i] <= w) {
        ans = max(ans, solve(i - 1, w - weight[i]) + value[i]);
    }

    return ans;
}

Этот код правильный по идее, но медленный. Он много раз пересчитывает одинаковые состояния.

Обычная рекурсия может работать примерно за O(2ⁿ), потому что каждый предмет дает два варианта: взять или не взять.

Рекурсия + мемоизация

Чтобы не пересчитывать одинаковые состояния, сохраняем ответы: 

dp[i][w]

Это ответ для состояния i, w.

Если ответ уже посчитан, возвращаем его: 

if (dp[i][w] != -1) {
    return dp[i][w];
}

Полная реализация: рекурсия + мемоизация

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int solve(int i, int w) {
    if (i == 0 || w == 0) {
        return 0;
    }

    if (dp[i][w] != -1) {
        return dp[i][w];
    }

    int ans = solve(i - 1, w);

    if (weight[i] <= w) {
        ans = max(ans, solve(i - 1, w - weight[i]) + value[i]);
    }

    dp[i][w] = ans;
    return dp[i][w];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    memset(dp, -1, sizeof(dp));

    cout << solve(n, W);

    return 0;
}

Как перевести в итеративный DP?

Было рекурсивно: 

solve(i, w)

Станет: 

dp[i][w]

Где:

dp[i][w] = максимальная ценность
если рассматриваем первые i предметов
и вместимость рюкзака равна w

Базовые значения

Если предметов 0, ответ 0: 

dp[0][w] = 0;

Если вместимость 0, ответ 0: 

dp[i][0] = 0;

Обычно глобальный массив уже заполнен нулями, поэтому отдельно можно не писать.

Итеративный переход

Для каждого предмета i и каждой вместимости w:

Не берем предмет: 

dp[i][w] = dp[i - 1][w];

Если можем взять предмет: 

dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);

Полная реализация 2D DP

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];

            if (weight[i] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << dp[n][W];

    return 0;
}

Пример входных данных

Input

3 5
3 10
2 7
4 12

Output

17

Здесь:

предмет 1: вес 3, ценность 10
предмет 2: вес 2, ценность 7
предмет 3: вес 4, ценность 12
W = 5

Лучший выбор — предмет 1 и предмет 2.

Как читать dp[i][w]?

Например: 

dp[3][5]

Это означает:

мы рассмотрели первые 3 предмета
вместимость рюкзака равна 5
какое максимальное value можно получить?

Ответ лежит в: 

dp[n][W]

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

В формуле: 

dp[i][w]

зависит только от предыдущей строки: 

dp[i - 1][...]

Поэтому можно использовать одномерный массив: 

dp[w]

Где dp[w] — лучший ответ для вместимости w.

Почему цикл идет справа налево?

Для 0/1 knapsack каждый предмет можно взять только один раз.

Поэтому при обновлении dp[w] нужно идти справа налево: 

for (int w = W; w >= weight[i]; w--)

Если идти слева направо, один и тот же предмет может использоваться несколько раз.

Главное правило 0/1 knapsack: цикл по весу идет от W к weight[i].

Полная реализация 1D DP

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, W;
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int w = W; w >= weight; w--) {
            dp[w] = max(dp[w], dp[w - weight] + value);
        }
    }

    cout << dp[W];

    return 0;
}

2D DP vs 1D DP

Метод Память Плюс Минус
2D DP O(nW) легко понять больше памяти
1D DP O(W) экономит память важен порядок цикла

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

Иногда нужно вывести не только максимальную ценность, но и какие предметы были выбраны.

Для этого удобнее использовать 2D DP.

Идем назад:

начинаем с i = n, w = W
если dp[i][w] == dp[i - 1][w], предмет i не взяли
иначе предмет i взяли

Код восстановления

vector<int> items;
int w = W;

for (int i = n; i >= 1; i--) {
    if (dp[i][w] == dp[i - 1][w]) {
        continue;
    }

    items.push_back(i);
    w -= weight[i];
}

reverse(items.begin(), items.end());

Полная реализация с восстановлением

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];

            if (weight[i] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << "Max value: " << dp[n][W] << '\n';

    vector<int> items;
    int w = W;

    for (int i = n; i >= 1; i--) {
        if (dp[i][w] == dp[i - 1][w]) {
            continue;
        }

        items.push_back(i);
        w -= weight[i];
    }

    reverse(items.begin(), items.end());

    cout << "Items: ";

    for (int x : items) {
        cout << x << ' ';
    }

    return 0;
}

Unbounded Knapsack

Есть другая версия рюкзака: каждый предмет можно брать сколько угодно раз.

Это называется:

unbounded knapsack
полный рюкзак

Здесь цикл по весу идет слева направо: 

for (int w = weight; w <= W; w++)

Полный рюкзак: реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, W;
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int w = weight; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weight] + value);
        }
    }

    cout << dp[W];

    return 0;
}
0/1 knapsack: цикл справа налево. Unbounded knapsack: цикл слева направо.

0/1 vs полный рюкзак

Тип Сколько раз можно взять предмет? Цикл по w
0/1 Knapsack 0 или 1 раз от W вниз
Unbounded Knapsack сколько угодно раз от weight вверх

Типичные ошибки

  • Не понять, что означает dp[i][w]
  • Перепутать вес и ценность
  • В 0/1 knapsack идти циклом слева направо
  • В полном рюкзаке идти циклом справа налево
  • Забыть проверить weight[i] <= w
  • Восстанавливать предметы по 1D DP, когда проще использовать 2D DP
  • Поставить слишком маленький размер массива

Асимптотика

Метод Время Память
Обычная рекурсия O(2ⁿ) O(n)
Мемоизация O(nW) O(nW)
2D DP O(nW) O(nW)
1D DP O(nW) O(W)

Как думать на задачах?

1. Что является предметом?
2. Что является весом?
3. Что является ценностью?
4. Предмет можно брать один раз или много раз?
5. Нужно максимум, минимум или количество способов?
6. Какой размер W?
7. Можно ли использовать O(nW)?

Короткий шаблон 0/1 Knapsack

int dp[W + 1];

for (int i = 1; i <= n; i++) {
    cin >> weight >> value;

    for (int w = W; w >= weight; w--) {
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

cout << dp[W];

Короткий шаблон полного рюкзака

int dp[W + 1];

for (int i = 1; i <= n; i++) {
    cin >> weight >> value;

    for (int w = weight; w <= W; w++) {
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

cout << dp[W];