Задача №1118. 0-1 Рюкзак
Динамическое программирование
Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.
Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?
Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.
Во второе строке вводятся N натуральных чисел mi, не превышающих 100.
Во третьей строке вводятся N натуральных чисел сi, не превышающих 100.
Выходные данные
Выведите наибольшую стоимость рюкзака.
Примеры
Входные данные
1 597 18 16
Выходные данные
16
Входные данные
2 27 30 35 3 9
Выходные данные
0
Сдать: для сдачи задач необходимо войти в систему