题解 | 【模板】01背包

#include<bits/stdc++.h>
using namespace std;
const int neg = -1000000;
int main(){
    int n,V;
    cin >> n >> V;
    vector<int >v(n), w(n);
    for(int i=0; i<n; i++){
        cin >> v[i] >> w[i];
    }
    // 1

    vector<int> dp1(V+1,0);
    for(int i=0; i<n; i++){
        for(int j=V; j>=v[i]; j--){
            dp1[j] = max(dp1[j], dp1[j-v[i]]+w[i]);
        }
    }
    cout << dp1[V] << endl;
    vector<int> dp2(V+1, -1);
    dp2[0] = 0;
    for(int i=0; i<n; i++){
        for(int j=V; j>=v[i]; j--){
            if(dp2[j-v[i]]!=-1){
                dp2[j] = max(dp2[j], dp2[j-v[i]]+w[i]);
            }
        }
    }
    if(dp2[V]==-1){
        cout << 0;
        return 0;
    }
    cout << dp2[V];
}