0

У меня есть вот такой код, который решает задачу о рюкзаке (надо из заданного набора предметов набрать вес W)

#include <bits/stdc++.h>

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, W;
    std::cin >> n >> W;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    sort(a.begin(), a.end());
    std::vector<int> dp(W + 1, 0);
    dp[0] = 1;
    std::vector<int> pr(W + 1, -1);
    for (int j = 0; j < n; ++j) {
        std::vector<int> temp = dp;
        for (int i = 0; i <= W; ++i) {
            if (i >= a[j] && temp[i - a[j]] > 0) {
                dp[i] += temp[i - a[j]];
                dp[i] = std::min(dp[i], 2);
                if (pr[i] == -1) {
                    pr[i] = i - a[j];
                }
            }
        }
    }
    if (dp[W] == 0) {
        std::cout << 0;
    } else if (dp[W] > 1) {
        std::cout << -1;
    } else {
        int i = W;
        std::vector<int> ans;
        while (pr[i] != -1) {
            ans.push_back(i - pr[i]);
            i = pr[i];
        }
        sort(ans.begin(), ans.end());
        std::cout << ans.size() << "\n";
        for (auto it : ans) {
            std::cout << it << " ";
        }
    }
}

Однако когда я меняю

for (int j = 0; j < n; ++j) {
        std::vector<int> temp = dp;
        for (int i = 0; i <= W; ++i) {
            if (i >= a[j] && temp[i - a[j]] > 0) {
                dp[i] += temp[i - a[j]];
                dp[i] = std::min(dp[i], 2);
                if (pr[i] == -1) {
                    pr[i] = i - a[j];
                }
            }
        }
    }

На это:

for (int j = 0; j < n; ++j) {
        for (int i = 0; i <= W; ++i) {
            if (i >= a[j] && dp[i - a[j]] > 0) {
                dp[i] += dp[i - a[j]];
                dp[i] = std::min(dp[i], 2);
                if (pr[i] == -1) {
                    pr[i] = i - a[j];
                }
            }
        }
    }

Код начинает работать по-другому, конкретно: Тест: 2 100 3 2 (из 2 предметов (3, 2) надо набрать вес 100) Первый вариант кода: вывод 0 Второй вариант кода: вывод -1

1 ответ 1

3

В первом варианте вы скопировали dp и меняете его значения с использованием тех значений, которые были в нем до изменений.

А во втором — вы меняете его значения с использованием уже измененных значений.

Разница очевидна?

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.