Дано N предметов массой m1,…,mN и стоимостью c1,…,cN соответственно. Ими наполняют рюкзак, который выдерживает вес не более M . Какую наибольшую стоимость могут иметь предметы в рюкзаке? Входные данные В первой строке вводится натуральное число N , не превышающее 100 и натуральное число M , не превышающее 10000 . Во второй строке вводятся N натуральных чисел mi , не превышающих 100 . Во третьей строке вводятся N натуральных чисел ci , не превышающих 100 . Выходные данные Выведите еди

Алгоритм решения этой задачи можно построить с использованием динамического программирования.

Шаги решения:
1. Считываем число N – количество предметов, и число M – вместимость рюкзака.
2. Считываем массивы mi и ci – массы и стоимости предметов соответственно.
3. Создаем двумерный массив dp размером (N+1) x (M+1). dp[i][j] будет содержать максимальную стоимость предметов, которые можно уложить в рюкзак вместимостью j, используя только первые i предметов.
4. Инициализируем dp[0][j] равными нулю, так как без предметов рюкзак пуст и его стоимость равна нулю.
5. Заполняем массив dp с помощью цикла по предметам от i=1 до N и вместимостям рюкзака от j=1 до M.
6. Если mi > j, то поместить предмет в рюкзак нельзя, поэтому dp[i][j] = dp[i-1][j] – берем предыдущую максимальную стоимость.
7. Если mi <= j, то есть есть возможность поместить предмет в рюкзак: - Если стоимость предмета плюс максимальная стоимость предметов без этого предмета (dp[i-1][j-mi]) больше максимальной стоимости предметов без этой массы (dp[i-1][j]), то помещаем предмет в рюкзак: dp[i][j] = ci + dp[i-1][j-mi]. - Иначе, не помещаем предмет в рюкзак: dp[i][j] = dp[i-1][j]. 8. Искомой наибольшей стоимостью будет dp[N][M]. Оценка времени работы этого алгоритма составляет O(N*M), где N - количество предметов, а M - вместимость рюкзака. Код решения можно реализовать на языке программирования, например, на Python или С++.