背包
01 背包
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
ans=max(ans,f[j]);
}
完全背包
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
ans=max(ans,f[j]);
}
多重背包
for(int i=1;i<=nt;i++)
{
int vt,wt,st; scanf("%d%d%d",&vt,&wt,&st);
int k=0;
while(k<=st)
{
v[++n]=vt<<k;
w[n]=wt<<k;
st-=1<<k;
k++;
}
if(st)
{
v[++n]=vt+st;
w[n]=wt*st;
}
}
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
ans=max(ans,f[j]);
}
分组背包
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=s[i];k++)
if(j>=v]i)[k] f[j]=max(f[j],f[j-v[i][k]]+w[i]);
标签:背包,int,max,--,ans,动态,规划,模板
From: https://www.cnblogs.com/jerrycyx/p/18444875