Условие:
Дано
N
N предметов массой
m
1
m
1
, …,
m
N
m
N
и стоимостью
c
1
c
1
, …,
c
N
c
N
соответственно.
Ими наполняют рюкзак, который выдерживает вес не более
M
M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?
Формат вывода
Выведите одно целое число: наибольшую возможную стоимость рюкзака.
Решение:
Для решения задачи о рюкзаке (задача о максимизации стоимости при ограничении на вес) можно использовать динамическое программирование. Вот пример кода на Python, который решает эту задачу: