背包分类

0-1背包

只用考虑物品放与不放

vector<int> volume(c) ;
for(int i = 1 ; i <= n ; ++i){
for(int j = c ; j >=weight[i] ; j--){
volume[j] = max(volume[j] , volume[j-weight[i]] + value[i]);

完全背包

每种物品数量不限

for(int i = 1 ; i <= n ; ++i){
for(int j = weight[i] ; j <= n ; ++j){
f[j] = max(volume[j] , volume[j-weight[i]] + value[i]);
}
}

限制背包

每种物品数量可能不止一个

for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=0;k<=c[i];k++){
if(j-k*a[i]<0)break;
f[j]=max(f[j],f[j-k*a[i]]+k*b[i]);
}

详细分析请看

算法实验之限制背包

谢谢访问