常用背包模板
背包问题主要是背模板,这一段时间一直在学习背包相关的问题,记录几个dp模板吧。
一些复杂的背包问题(如泛化物品)未收录
01背包问题:
无优化
1
2
3
4
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]);
}
}
一维数组优化:
1
2
3
4
5
6
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]);
}
}
更进一步的常数优化:
1
2
3
4
5
6
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]);
}
}
完全背包问题:
1
2
3
4
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]);
}
}
多重背包问题:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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=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]);
}
}
}
This post is licensed under CC BY 4.0 by the author.