题解 | 【模板】01背包（优化）

#include <iostream>
#include <vector>
#include<algorithm>
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<int> dp1(V+1),dp2(V+1);
    //dp2初始化
    for(int j=1;j<=V;j++) dp2[j]=-1;
    

    //填表
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=num[i][0];j--)
        {
            dp1[j]=max(dp1[j],dp1[j-num[i][0]]+num[i][1]);
            if(dp2[j-num[i][0]]!=-1) 
                dp2[j]=max(dp2[j],dp2[j-num[i][0]]+num[i][1]);
        }
    }

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