题解 | 【模板】完全背包

#include <bits/stdc++.h>

using namespace std;

const int MN=1010;

int N, V;
int v[MN], w[MN], f1[MN], f2[MN];   //f1/2[V]表示容量不超过/恰好等于V的最大价值

int main()
{
    cin>>N>>V;
    memset(f2, -1, sizeof f2);
    f2[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[i]; j<=V; j++)
            {
                f1[j]=max(f1[j], f1[j-v[i]]+w[i]);
                if(f2[j-v[i]]!=-1) f2[j]=max(f2[j], f2[j-v[i]]+w[i]);
            }
    f2[V]=max(0, f2[V]);

    cout<<f1[V]<<"\n"<<f2[V];
    return 0;
}
/*
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

可推导出 f[i,j]=max(f[i-1,j], f[i][j-v]+w[i])
*/

/*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++)
            for(int k=0; k*v[i]<=j; k++)
                f[i][j]=max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]);
                
    cout<<f[N][V];
    return 0;
    
}*/

第一问就是完全背包的裸题，推导可以看注释代码

第二问可以初始时只让f2[0]合法，转移时避免了从非法状态转移过了

即可愉快ac！

#牛客春招刷题训练营#