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

#include <bits/stdc++.h>

using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, v;
    cin >> n >> v;
    vector<int> dp1(v + 1, 0); //表示最大容量
    vector<int> dp2(v + 1, 0); //表示装满后最大价值
    vector<int> dp3(v + 1, 0); //表示最大价值
    vector<pair<int, int>> num(n, make_pair(0, 0));
    for (int i = 0; i < n; i++) {
        cin >> num[i].first >> num[i].second;
    }
    sort(num.begin(), num.end());
    
    reverse(num.begin(), num.end());
    for (int i = n - 1; i >= 0; i--) {
        for (int j = v; j >= num[i].first; j--) {
            dp1[j] = max(dp1[j], dp1[j - num[i].first] + num[i].first);
            if(j == dp1[j]) {
                dp2[j] = max(dp2[j], dp2[j - num[i].first] + num[i].second);
            }
            dp3[j] = max(dp3[j], dp3[j - num[i].first] + num[i].second);
        }
    }
    
    cout << dp3[v] << endl << dp2[v] << endl;
    return 0;
}