- 01背包：所谓01背包，就是每种物体有一个价值且数量只有一个，给定一个背包容量，在不超出背包容量的前提下在n个物体中取m个，求最大价值。
点击查看代码
//f[i]指体积为i时的最大价值
for(int i=1;i<=n;i++){//第一层循环是指遍历每种物体，n是物体种数
for(int j=m;j>=v[i];j--){//第二层是选取物体，倒序是为了保留上一行状态
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
- 完全背包：所谓完全背包，就是每种物体有一个价值且数量有无数个，给定一个背包容量，在不超出背包容量的前提下在n种物体中取m个，求最大价值。
点击查看代码
for(int i=1;i<=n;i++){//第一层循环是指遍历每种物体，n是物体种数
for(int j=v[i];j<=m;j++){//第二层还是选取物体，但正序恰好代表对一个物品的无限制重复计算，刚好就是完全背包。
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
- 多重背包：所谓完全背包，就是每种物体有一个价值且数量有k个，给定一个背包容量，在不超出背包容量的前提下在n种物体中取m个，求最大价值。
点击查看代码
for(int i=1;i<=n;i++){
for(int j=1;j<=ge[i];j++){//这里相对于只是在01背包的基础上加了一个个数上的枚举（如果觉得效率低可以用二进制优化，详见下）
for(int k=m;k>=v[i];k--){
f[k]=max(f[k],f[k-v[i]]+e[i].w);
}
}
}
//二进制优化:就是指一个数可以拆分成许多个二进制的数来表示，这比一个一个去加要快很多
for(int i=1;i<=n;i++){
scanf("%d%d%d",&vi,&wi,&si);//体积，价值，个数
if(si>m/vi) si=m/vi;//m表示最大背包容量，如果个数大于能放的最大个数，直接换掉就行
//转二进制
for(int j=1;j<=si;j<<=1){
v[++cnt]=j*vi;
w[cnt]=j*wi;
si-=j;
}
//剩余的单成一组
if(si>0){
v[++cnt]=si*vi;
w[cnt]=si*wi;
}
}
-
混合背包：所谓混合背包，就是把1，2，3种背包合并到一起，一道题里啥都有，这种只需要全转成01背包就行，不多解释。
-
分组背包：有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
点击查看代码
//r物品组数，n背包容量
for(int i=1;i<=r;i++){//遍历每组物品
for(int j=n;j>=0;j--){背包容量
for(int k=1;k<=s[i];k++){决策，保证每组只选一个
if(j>=w[i][k])f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
}
}
}