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

#include <cstdint>
#include <cstring>
#include <iostream>
#include <ostream>
using namespace std;
int const N=1010;
int w[N],v[N];
int f[N];
int n,V;
int main()
{

    cin>>n>>V;
    w[0]=0;v[0]=0;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    //此时不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品
    memset(f, 0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    cout<<f[V]<<endl;
    //此时考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品
    memset(f, -100,sizeof(f)); //-100表示一个极小的值，可以用任意类型中最小的值表示，这里用-100
    f[0]=0;//没有物品时，价值为0
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    //输出防止输出小于0的数,即返回值必须大于等于0
    cout<<(f[V]<0?0:f[V])<<endl;
}