Сложнаяdp
Рюкзак (0-1)
Лимит времени 2 с · Память 64 МБПринято: —Решили: 0
Условие
В первой строке даны число предметов n и вместимость рюкзака W. В каждой из следующих n строк даны вес w и ценность v предмета. Выведите наибольшую суммарную ценность набора предметов с общим весом не более W. Каждый предмет можно взять не более одного раза.
Примеры
Пример 1
Ввод
3 8 3 30 4 50 5 60
Вывод
90
Пример 2
Ввод
1 1 2 100
Вывод
0
Ограничения
- 1 ≤ n ≤ 100
- 1 ≤ W ≤ 10^4
- 1 ≤ w ≤ 10^4
- 1 ≤ v ≤ 10^9