【每日刷题】Day151

🥕个人主页： 开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

【模板】01背包_牛客题霸_牛客网

【模板】01背包_牛客题霸_牛客网

//思路：动态规划

#include <iostream>

#include <vector>

using namespace std;

int n,V;

int main()

{

    cin>>n>>V;

    vector<int> v(1010);//体积

    vector<int> w(1010);//价值

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

    vector<vector<int>> dp1(n+1,vector<int>(1010));

    vector<vector<int>> dp2(n+1,vector<int>(1010));

    for(int j = 1;j<=V;j++) dp2[0][j] = -1;

    for(int i = 1;i<=n;i++)

    {

        for(int j = 1;j<=V;j++)

        {

//第一个问题，背包不必要装满

            dp1[i][j] = dp1[i-1][j];

            if(j-v[i]>=0)

                dp1[i][j] = max(dp1[i][j],dp1[i-1][j-v[i]]+w[i]);

//第二个问题，背包必须恰好装满

            dp2[i][j] = dp2[i-1][j];

            if(j-v[i]>=0&&dp2[i-1][j-v[i]]!=-1)

                dp2[i][j] = max(dp2[i][j],dp2[i-1][j-v[i]]+w[i]);

        }

    }

    cout<<dp1[n][V]<<endl;

    cout<<(dp2[n][V]==-1?0:dp2[n][V])<<endl;

    return 0;

}