Задача о рюкзаке является классическим примером использования динамического программирования. В данной задаче мы будем решать задачу о 0/1 рюкзаке, где каждый предмет можно взять только один раз. Давайте разберем, как это сделать на C++ в функции int main().

Для решения этой задачи мы будем использовать массив dp, где dp[j] будет хранить максимальную стоимость, которую можно получить с рюкзаком, имеющим вместимость j.

Вот шаги, которые мы будем выполнять:

1. Считываем входные данные: количество предметов N, максимальный вес рюкзака M, массив масс m и массив стоимостей c.
2. Создаем массив dp размером M + 1 и инициализируем его нулями.
3. Для каждого предмета проходим по массиву dp в обратном порядке, начиная с M и заканчивая весом предмета. Это делается для того, чтобы не перезаписать значения, которые мы еще не использовали.
4. В каждом шаге обновляем dp[j] как максимальное значение между dp[j] и dp[j - m[i]] + c[i], если j больше или равен массе предмета.
5. После обработки всех предметов максимальная стоимость будет находиться в dp[M].

Теперь давайте посмотрим на код:

#include <iostream> #include <vector> int main(){int N, M; std::cin >> N >> M; std::vector m(N),c(N); for (int i = 0; i < N; ++i){std::cin >> m[i]; }for (int i = 0; i < N; ++i){std::cin >> c[i]; }std::vector dp(M + 1, 0); for (int i = 0; i < N; ++i){for (int j = M; j >= m[i]; --j){dp[j] = std::max(dp[j], dp[j - m[i]] + c[i]); }}std::cout << dp[M] << std::endl; return 0; }

В этом коде:

• Сначала мы считываем количество предметов и максимальную массу рюкзака.
• Далее считываем массивы масс и стоимостей.
• Инициализируем массив dp нулями.
• Заполняем массив dp по описанному алгоритму.
• Выводим максимальную стоимость, которую можно получить с рюкзаком максимальной вместимости.

Таким образом, мы решаем задачу о рюкзаке с использованием динамического программирования. Этот подход позволяет эффективно находить решение за время O(N * M),что приемлемо для заданных ограничений.