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

Информатика 11 класс Динамическое программирование задача о рюкзаке динамическое программирование C++ код функции main максимальная стоимость рюкзак N предметов веса и стоимости алгоритм программирование Новый

Задача о рюкзаке является классическим примером использования динамического программирования. В данной задаче мы будем решать задачу о 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), что приемлемо для заданных ограничений.