Рюкзак туриста

1. Идея

Это классическая задача о рюкзаке 0/1: у каждого предмета есть масса w_i и полезность v_i, и каждый предмет можно взять либо один раз, либо не брать совсем.

Нужно максимизировать суммарную полезность, не превышая ограничение по массе W.

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

Будем хранить dp[c] — максимальную полезность, которую можно получить, если использовать рюкзак вместимости c.

Тогда, когда мы рассматриваем очередной предмет массы w и полезности v, для каждой вместимости c >= w можно:

• не брать предмет, тогда остаётся dp[c],
• взять предмет, тогда получится dp[c - w] + v.

Берём максимум из этих двух вариантов.

2. Наблюдения

Наблюдение 1

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

Но здесь каждый предмет можно взять не более одного раза, поэтому обновление нужно делать справа налево: от W до w.

Это гарантирует, что один и тот же предмет не будет использован несколько раз в рамках одной итерации.

Наблюдение 2

Хотя в условии нужно найти ответ для массы не больше W, достаточно вывести dp[W].

Почему это корректно: если рюкзак можно заполнить не полностью, то значение dp[c] для больших c не хуже, чем для меньших, потому что можно просто не использовать лишнюю вместимость. Значит, dp[W] уже содержит лучший ответ среди всех масс от 0 до W.

Наблюдение 3

Полезности могут быть большими: v_i до 10^9, а предметов до 1000, поэтому сумма может быть до 10^12. Значит, в C++ нужно использовать тип long long.

3. Алгоритм

1. Считываем n и W.
2. Создаём массив dp длины W + 1, заполненный нулями.
   • dp[c] — максимальная полезность для вместимости c.
3. Для каждого предмета с массой w и полезностью v:
   • перебираем c от W до w,
   • обновляем:
     • dp[c] = max(dp[c], dp[c - w] + v).
4. Выводим dp[W].

4. Почему это работает

Докажем корректность идеи.

После обработки нескольких первых предметов dp[c] будет означать максимальную полезность, которую можно получить, используя только эти предметы и имея ограничение по массе c.

База

До обработки предметов никакие вещи не выбраны, поэтому для любой вместимости c максимальная полезность равна 0. Именно так и инициализируется массив dp.

Переход

Пусть сейчас рассматривается предмет с массой w и полезностью v.

Для любой вместимости c возможны два случая:

1. Не брать этот предмет.
   Тогда лучшая полезность остаётся прежней: dp[c].

2. Взять этот предмет, если c >= w.
   Тогда нужно оставить место w под этот предмет, а оставшуюся вместимость c - w оптимально заполнить уже рассмотренными ранее предметами. Получаем значение dp[c - w] + v.

Значит, лучший вариант: max(dp[c], dp[c - w] + v).

Почему перебор идёт справа налево

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

Если бы мы шли слева направо, то при вычислении dp[c] значение dp[c - w] могло бы уже быть обновлено этим же предметом. Тогда один и тот же предмет использовался бы несколько раз.

Перебор справа налево гарантирует, что dp[c - w] ещё относится к состоянию до добавления текущего предмета. Значит, каждый предмет учитывается не более одного раза.

Следовательно, после обработки всех n предметов dp[W] действительно равно максимальной суммарной полезности при массе не больше W.

5. Сложность

Для каждого из n предметов мы перебираем все вместимости от W до w.

Итоговая сложность:

• по времени: O(n * W)
• по памяти: O(W)

При ограничениях n <= 1000 и W <= 10^5 это решение подходит.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, W;
    cin >> n >> W;

    vector<long long> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        int w;
        long long v;
        cin >> w >> v;

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

    cout << dp[W] << '\n';
    return 0;
}

7. Код на Python 3

n, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(n):
    w, v = map(int, input().split())
    for c in range(W, w - 1, -1):
        candidate = dp[c - w] + v
        if candidate > dp[c]:
            dp[c] = candidate

print(dp[W])