Рюкзак охотника за реликвиями

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

Найди максимальную суммарную пользу, которую можно унести.

Формат ввода

В первой строке два целых числа n и W — число артефактов и вместимость рюкзака. Далее идут n строк: в каждой два целых числа wi и vi — вес (сколько места занимает) и польза артефакта.

Формат вывода

Выведи одно целое число — максимальную суммарную пользу, которую можно получить, выбрав некоторые артефакты так, чтобы суммарный вес не превышал W.

Ограничения

• 1 ≤ n ≤ 80
• 1 ≤ W ≤ 4000
• 1 ≤ wi ≤ 1000
• 1 ≤ vi ≤ 1000

Пример

Ввод:

4 7
3 4
4 5
2 3
3 4

Вывод:

9

Пояснение: можно взять артефакты с весами 3 и 4 (польза 4 + 5 = 9).

Ключевое наблюдение: каждый артефакт можно взять не больше одного раза, значит для каждого предмета выбор бинарный — «взять» или «пропустить». Если уметь быстро отвечать на вопрос «какая лучшая польза при вместимости c, рассматривая только первые i предметов», то следующий предмет добавляется локальным решением.

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

• не берём i-й: остаёмся на dp[i-1][c]
• берём i-й (если c >= wi): получаем dp[i-1][c-wi] + vi

И берём максимум: dp[i][c] = max(dp[i-1][c], dp[i-1][c-wi] + vi).

План решения:

• Считать n, W и список пар (wi, vi).
• Создать таблицу dp размера (n+1) x (W+1), нулевая строка = 0 (без предметов пользы нет).
• Для i от 1 до n:
• для всех c от 0 до W посчитать dp[i][c] по формуле выше.
• Ответ — dp[n][W].

Сложность: O(n*W) по времени (до 80*4000 = 320k операций) и O(n*W) по памяти. Можно сжать до O(W), но тогда важно обновлять c в обратном порядке.

Частая ошибка: при переходе брать значение только из предыдущей строки (i-1). Если в 1D-версии идти по c вперёд, один и тот же предмет начнёт «использоваться несколько раз» (получится не 0/1, а бесконечный рюкзак).