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

#include <vector>
#include <iostream>
#include <limits.h>

using namespace std;

int compute(int n, int V, vector<vector<int>>& vw, vector<int>& dp)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = vw[i][0]; j <= V; j++)
        {
            dp[j] = max(dp[j], dp[j-vw[i][0]] + vw[i][1]);
        }
    }
    
    return dp[V];
}

int fullbag(int n, int V, vector<vector<int>>& vw, bool p1) {
    
    int ret = 0;
    if (p1){
        vector<int> dp(V+1, 0);
        ret = compute(n, V, vw, dp);
    }
    else
    {
        vector<int> dp(V+1, INT_MIN);
        dp[0] = 0;
        ret = compute(n, V, vw, dp);
        if (ret < 0) ret = 0;
    }

    return ret;
}


int main()
{
    int n, V;
    cin >> n >> V;
    vector<vector<int>> vw;
    
    for (int i = 0; i < n; i++)
    {
        int v, w;
        vector<int> tmp;
        cin >> v >> w;
        tmp.push_back(v);
        tmp.push_back(w);
        vw.push_back(tmp);
    }
    

    cout << fullbag(n, V, vw, true) << endl;
    cout << fullbag(n, V, vw, false) << endl;
    
    return 0;
}