【模板】01背包

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e3 + 10;
const int M = 2e4 + 10;
const int mod  = 1e9 + 7;
int dp[N];   
int v[N],w[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j-v[i]] + w[i],dp[j]);
        }
    }
    cout<<dp[m]<<endl;
    /**
     * 类似01背包，不同的是需要初始化dp为负无穷
     */
    memset(dp,-0x3f3f3f,sizeof dp);
    //初始化为负无穷，这样如果dp[j-v[i]]不能到达，dp[j]也不能到达
    //因为dp[i-v[i]]没到达则为负无穷，负无穷加一个w[i]也为负无穷
    //需要注意的是dp[0]需要初始化为0，因为容积为0不放任何东西是合法的
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j-v[i]] + w[i],dp[j]);
        }
    }
    if(dp[m] < 0){
        cout<<"0";  //不能到达体积为m
    } else{
        cout<<dp[m];
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}