题解 | #【模板】完全背包#

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int main() {
    int n, v;
    cin >> n >> v;
    vector<int> val(n);
    vector<int> w(n);
    for(int i=0; i<n; i++)
    cin >> w[i] >> val[i];

    vector<int> dp1(v+1, 0);
    vector<int> dp2(v+1, -N);
    dp2[0] = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=w[i]; j<=v; j++)
        {
            dp1[j] = max(dp1[j], dp1[j-w[i]] + val[i]);
            dp2[j] = max(dp2[j], dp2[j-w[i]] + val[i]);
        }
    }
    if(dp2[v] < 0)dp2[v] = 0;
    cout << dp1[v] << endl;
    cout << dp2[v];
}
// 64 位输出请用 printf("%lld")