Контест Middle Задачи на Java обновлено
Рюкзак 0/1
Условие
Есть n предметов с весом и ценностью и рюкзак вместимостью W. Каждый предмет можно взять не больше одного раза. Найдите максимальную суммарную ценность.
Ввод: в первой строке n и W (1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴), далее n строк вес ценность (1 ≤ вес ≤ 10⁴, 0 ≤ ценность ≤ 10⁹).
Вывод: одно число.
Пример
4 7
1 1
3 4
4 5
5 7
9
Как подойти
DP по вместимости, обход с конца.
Подсказки: 2
- Одномерный массив, но обход вместимостей в обратном порядке.
- Ценности в сумме больше int.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.