背包九讲练习题

01背包

有N种物品和一个容量为V的背包，每种物品只有1个，第i种物品的体积为v[i]，价值为w[i]。问将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大，输出最大值。
0<N,V<=1000; 0<v[i],w[i]<=1000

#include <bits/stdc++.h>
int main() {
    int N, V;
    std::cin >> N >> V;
    std::vector<int> v(N), w(N);
    for (int i = 0; i < N; i++) {
        std::cin >> v[i] >> w[i];
    }
    std::vector<int> dp1(V + 1), dp2(V + 1);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            dp2[j] = dp1[j];
            if (j >= v[i-1]) {
                dp2[j] = std::max(dp2[j], w[i-1] + dp1[j-v[i-1]]);
            }
        }
        std::swap(dp1, dp2);
    }
    std::cout << dp1[V] << "\n";
    return 0;
}

完全背包

有N种物品和一个容量为V的背包，每种物品有无限多个，第i种物品的体积为v[i]，价值为w[i]。问将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大，输出最大值。
0<N,V<=1000; 0<v[i],w[i]<=1000

#include <bits/stdc++.h>
int main() {
    int N, V;
    std::cin >> N >> V;
    std::vector<int> v(N), w(N);
    for (int i = 0; i < N; i++) {
        std::cin >> v[i] >> w[i];
    }
    std::vector<int> dp1(V + 1), dp2(V + 1);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            dp2[j] = dp1[j];
            if (j >= v[i-1]) {
                dp2[j] = std::max(dp2[j], w[i-1] + dp2[j-v[i-1]]);
            }
        }
        std::swap(dp1, dp2);
    }
    std::cout << dp1[V] << "\n";
    return 0;
}