题解 | 【模板】01背包

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

int main() {
    int n,V;
    cin>>n>>V;
    vector<vector<int>> arr(n,vector<int>(2,0));
    for(int i=0;i<n;i++){
        cin>>arr[i][0]>>arr[i][1];
    }
    //dp1[i]表示容量i所获得的总价值
    vector<int> dp1(V+1,0);
    for(int i=0;i<n;i++){
        int v=arr[i][0];
        for(int j=V;j>=v;j--){
            dp1[j]=max(dp1[j],dp1[j-v]+arr[i][1]);
        }
    }
    cout<<dp1[V]<<endl;
    //dp2[i]表示刚好装满i所得到的最大价值
    vector<int> dp2(V+1,INT_MIN);
    dp2[0]=0;
    for(int i=0;i<n;i++){
        int v=arr[i][0];
        for(int j=V;j>=v;j--){
            if(dp2[j-v]!=INT_MIN){
                dp2[j]=max(dp2[j],dp2[j-v]+arr[i][1]);
            }
        }
    }
    cout<<(dp2[V]==INT_MIN?0:dp2[V])<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")