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

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

01背包问题：

无优化

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

一维数组优化：

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

更进一步的常数优化：

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

完全背包问题：

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

多重背包问题：

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