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

#include<iostream>
#include<climits>
using namespace std;
struct node{
    int val;
    int weight;
}t[1001];
int dp[1001][1001] = {0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,v,ans1,ans2 = 0;
    cin >> n >> v;
    for(int i = 1;i <= n;++i)
        cin >> t[i].weight >> t[i].val;
    for(int i = 0;i <= n;++i){
        for(int j = 0;j <= v;++j){
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else{
                if(j >= t[i].weight)
                    dp[i][j] = max(dp[i][j - t[i].weight] + t[i].val,dp[i - 1][j]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
    }
    ans1 = dp[n][v];
    for(int i = 0;i <= n;++i)
        for(int j = 0;j <= v;++j)
            dp[i][j] = INT_MIN;
    dp[0][0] = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 0;j <= v;++j){
            if(j >= t[i].weight)
                dp[i][j] = max(dp[i][j - t[i].weight] + t[i].val,dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    if(dp[n][v] < 0)
        ans2 = 0;
    else
        ans2 = dp[n][v];
    cout << ans1 << endl << ans2;
}