题解 | 【模板】01背包

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1010;

int N, V;
int v[MAXN], w[MAXN], f[MAXN], dp[MAXN];

int main()
{
    cin>>N>>V;
    memset(dp, -1, sizeof dp);
    dp[0]=0;
    for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
    
    for(int i=1; i<=N; i++)
        for(int j=V; j>=v[i]; j--)//倒序滚动是因为max(f[i-1][j], f[i-1][j-v[i]]+w[i]中j-v[i]一定小于j，此时未更新，用的就是i-1时的数据
        {
            f[j]=max(f[j], f[j-v[i]]+w[i]);
            if(dp[j-v[i]]!=-1) dp[j]=max(dp[j], dp[j-v[i]]+w[i]);
        }    
    dp[V]=max(0, dp[V]);
    
    cout<<f[V]<<"\n"<<dp[V];
    return 0;
}
/*int main()
{
    cin>>N>>V;
    for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=N;i++)
        for(int j=0;j<=V;j++)
            if(j<v[i]) f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
    
    cout<<f[N][V];
    return 0;
}*/

第一问就是01背包，在代码中下面给出了二维的推导，可以对代码等价变形得到一维的

第二问可以初始dp[0]合法，转移时只能从合法状态转移过来

可以手推一下

#牛客春招刷题训练营#