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

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

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

Формат ввода

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

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

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

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ n ≤ 80
• 1 ≤ W ≤ 4000
• 1 ≤ wi ≤ 1000
• 1 ≤ vi ≤ 1000
• Суммарное число артефактов во всех наборах данных не превышает 80.
• Суммарная вместимость рюкзаков во всех наборах данных не превышает 4000.

Пример

Ввод:

3
1 1
1 1000
2 5
5 1000
1 1
4 7
3 4
4 5
2 3
3 4

Вывод:

1000
1000
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, а бесконечный рюкзак).