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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int main() {
    int n, nv;
    cin >> n >> nv;
    vector<int>v(n, 0), w(n, 0);
    // 这里的取值是关键
    vector<int>dp(nv + 1, -N);

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

    dp[0] = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = nv; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]); 
        }
    }
    int m = *max_element(dp.begin(), dp.end());
    cout << m << endl;

    if(dp[nv] < 0)dp[nv] = 0;
    cout << dp[nv];
}
// 64 位输出请用 printf("%lld")