阿毛の次元

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]);
    }
}

READ MORE →