题解 | #【模板】01背包#

#include <iostream>
#include<bits/stdc++.h>

#include <vector>
using namespace std;

int main() {
    int n,V;
    cin>>n>>V;
    vector<int >v(n+1,0);
    vector<int>w(n+1,0);
    vector<int>dp1(V+1,0);
    vector<int>dp2(V+1,-11111111);//恰好装满问题与经典问题的主要区别在于dp数组的初始化不能是0
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    dp2[0]=0;//但是dp[0]必须是0
    for(int i=1;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;
    for(int i=1;i<=n;i++){
        for(int j=V;j>=v[i];j--){
            dp2[j]=max(dp2[j],dp2[j-v[i]]+w[i]);
        }
    }
    if(dp2[V]>0）//如果小于0是装不满情况，属于无效解
    cout<<dp2[V]<<endl;
    else
     cout<<"0";
}
// 我觉得经典01背包问题理解不了的话就背下来吧