题解 | 【模板】01背包

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    //动态规划
    //第一问：
    //dp[i][j]表示从前i个物品中选，总体积不超过j的所有选法中
    //价值最大的选法

    //第二问：
    //dp[i][j]表示从前i个物品中选，总体积恰好为j的所有选法中
    //价值最大的选法

    //前置工作
    int n=0,V=0;
    cin>>n>>V;
    //第一列记录物品体积，第二列记录物品价值
    vector<vector<int>> num(n+1,vector<int>(2));
    int v=0,w=0;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w;
        num[i][0]=v,num[i][1]=w;
    }

    //开始动态规划
    vector<vector<int>> dp1(n+1,vector<int>(V+1));
    vector<vector<int>> dp2(n+1,vector<int>(V+1));
    //dp2的初始化
    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-num[i][0]>=0) 
                dp1[i][j]=max(dp1[i][j],dp1[i-1][j-num[i][0]]+num[i][1]);
            dp2[i][j]=dp2[i-1][j];
            if(j-num[i][0]>=0&&dp2[i-1][j-num[i][0]]!=-1)
                dp2[i][j]=max(dp2[i][j],dp2[i-1][j-num[i][0]]+num[i][1]);
        }
    }

    //方案1答案
    cout<<dp1[n][V]<<endl;
    //方案2答案
    int ret2=dp2[n][V]==-1?0:dp2[n][V];
    cout<<ret2;
}