阿毛の次元

Amaok – 修合无人见,存心有天知。

常用背包模板

背包问题主要是背模板,这一段时间一直在学习背包相关的问题,记录几个dp模板吧。

一些复杂的背包问题(如泛化物品)未收录

01背包问题:

无优化

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;c++)
    {
        f[i][j]=f[i-1][j];
        if(j>=w[i])
        f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
    }
}

一维数组优化:

for(int i=1;i<=n;i++)
{
    for(int j=m;j>=0;j--)
    {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}

更进一步的常数优化:

for(int i=1;i<=n;i++)
{
    sumw+=w[i];
    bound=max(m-sumw,w[i]);
    for(int j=m;j>=bound;j--)
    {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}

完全背包问题:

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}

多重背包问题:

for(int i=1;i<=n;i++)
{
    if(w[i]*a[i]>m)
    {
        for(int j=0;j<=m;j++)
        {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    else
    {
         k=1;amount=a[i];
         while(k<amount)
         {
             for(int j=k*w[i];j>=0;j--)
             {
                 if(j>=w[i])
                 f[j]=max(f[j],f[j-w[i]]+k*v[i]);
             }
             amount-=k;
             k<<=1;
         }  
         for(int j=amount*w[i];j>=0;j--)
         {
             f[j]=max(f[j],f[j-w[i]]+amount*v[i]);
         }
    } 
}