题解 | 【模板】01背包

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;

    vector<int> w(n), v(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }

    // 方案1：不要求刚好装满
    vector<int> dp1(V + 1, 0);
    // 方案2：要求刚好装满
    vector<int> dp2(V + 1, -1); // -1 表示无法达到该体积
    dp2[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= w[i]; --j) {
            // 方案1：不要求刚好装满
            dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);

            // 方案2：要求刚好装满
            if (dp2[j - w[i]] != -1) {
                dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i]);
            }
        }
    }

    cout << dp1[V] << endl;
    cout << (dp2[V] == -1 ? 0 : dp2[V]) << endl;
    return 0;
}