1.01背包问题
顾名思义，及每种物品可以选择放或不放，于是就有了最朴素的转移式：f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]},然后考虑优化空间,可转换为f[j]=max(f[j],f[j-w[i]]+c[i])注意j要逆序的从m到1（保证从已决定推到未决定）；
2.完全背包问题
与01背包类似，但是关键的不同在于其j要顺序的从1到n，因为需要一个可能已选的子结果，然后同理可得f[j]=max(f[j],f[j-w[i]]+c[i])；
3.多重背包问题
基本想法是f[i][v]=max(f[i][j],f[i-1][j-k*w[i]+k*c[i]),(0<=k<=n[i]&&k*w[i]<=j);转换为01背包问题即把每一个拆分为n[i]个，这样时间和空间的复杂度为O(V*sum(n[i]));然后考虑优化，把每件物品分成若干件2^0,2^1,2^2,2^3,2^(k-1),n[i]-2^k+1(即剩下的)，这样既可把时间和空间复杂度降一个log.
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n,cnt,m; int f[10010]; int p[10010],c[10010]; int main(){ scanf("%d%d",&n,&m); int x,y,z,t; for(int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); t=1; while(z>=t){//转换 p[++cnt]=x*t; c[cnt]=y*t; z-=t; t*=2; } p[++cnt]=x*z; c[cnt]=y*z; } for(int i=1;i<=cnt;i++)//01背包 for(int j=m;j>=p[i];j--) f[j]=max(f[j],f[j-p[i]]+c[i]); printf("%d",f[m]); return 0; }
4、二维费用
其实并没有什么不同，就是在前三个的基础上再加一个状态f[i][v][u]=max(f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]);
例题：潜水员https://blog.csdn.net/sslgz_yyc/article/details/70337182；
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int v,u,n; int a[1010],b[1010],c[1010]; int f[1010][1010]; int main(){ scanf("%d%d%d",&v,&u,&n); //求最小值要注意先初始化较大值 memset(f,127,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(int i=1;i<=n;i++) for(int j=v;j>=0;j--) for(int k=u;k>=0;k--){ int x1=min(v,j+a[i]),x2=min(u,k+b[i]); f[x1][x2]=min(f[x1][x2],f[j][k]+c[i]); } printf("%d",f[v][u]); }
5、依赖性
例题 https://www.luogu.org/problemnew/show/P1064；金明的预算方案，这道题就提到从属关系，但是注意到附件最多有两个，所以在01背包的基础上再加上三次比较即可。
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; //在01背包的基础上弄4次判断；（因为附件最多两件） int n,m; int a[60][3]; int v[100],w[100]; int f[100100]; int max(int x,int y){ return x>y?x:y; } int main(){ scanf("%d%d",&n,&m); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); v[i]=x; w[i]=y; if(z==0)a[i][0]=i; else{ if(a[z][1]==0)a[z][1]=i; else a[z][2]=i; } } for(int i=1;i<=m;i++) if(a[i][0]) for(int j=n;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]); if(a[i][1]&&j>=v[i]+v[a[i][1]]) f[j]=max(f[j],f[j-v[i]-v[a[i][1]]]+v[i]*w[i]+v[a[i][1]]*w[a[i][1]]); if(a[i][2]&&j>=v[i]+v[a[i][2]]) f[j]=max(f[j],f[j-v[i]-v[a[i][2]]]+v[i]*w[i]+v[a[i][2]]*w[a[i][2]]); if(a[i][1]&&a[i][2]&&j>=v[i]+v[a[i][1]]+v[a[i][2]]) f[j]=max(f[j],f[j-v[i]-v[a[i][1]]-v[a[i][2]]]+v[i]*w[i]+v[a[i][1]]*w[a[i][1]]+v[a[i][2]]*w[a[i][2]]); } printf("%d",f[n]); return 0; }
然后我们考虑将其推广为附件没有被限制个数的问题。第一反应是如原来那样枚举，但是显然时间会超，因为每次只能选择一中策略，所以一个主件和附件几何即为一个物品组，每个策略对应一件物品，所以我们先对主件i的附件合集进行一个01背包，就可将其转换为V-w[i]+1个物品，对于一个费用为w[i]+k的价值为f[k]+c[i];然后就...;
#include<cstring> #include<cstdio> #include<algorithm> #include <iostream> using namespace std; const int maxn=1000+10; int w[maxn],b[maxn]; int f[maxn]; int max(int a,int b) { return a>b? a:b; } int main() { int n,v; int i,j,k; int t1,t2; while(scanf("%d%d",&n,&v)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%d",&w[i],&b[i]); } memset(f,0,sizeof(f)); for(i=1;i<=n;i++) if(b[i]==i)//找出主件 { memset(c,0,sizeof(c)); for(t2=1;t2<=n;t2++)//对附件进行01背包处理，使得在相同体积下得到的价值最大 if(b[t2]==i&&b[t2]!=t2) {for(t1=v-1;t1>=0;t1--) if(t1-1>=0) c[t1]=max(c[t1],c[t1-1]+w[t2]); } c[v]=c[v-1]+w[i]; for(j=v;j>=0;j--) for(k=1;k<=v;k++)//此时看作相当于"V件物品"，每件”物品体积“相当为'k',"价值为"，c[k-1]+w[i],(i为主件) {if(j-k>=0) f[j]=max(f[j],f[j-k]+w[i]+c[k-1]); } } printf("%d ",f[v]); } return 0; }
6.方案总数
其实非常的简单，改成和就可以。
7.比较
1、首先便是01背包和完全背包的比较，这两类其实区别很明显，一个是只有一个，一个是无限个数，而使用方法就要注意，唯一的差别是01背包是逆序的，完全背包是顺序的（J的循环）时间复杂度都近似于O(nm),而空间复杂度皆为O(m);
2、多重背包特点是每类有有限个的选取个数，二维费用则是有两个限制条件，注意两者都是建立在01背包的基础上；
3、依赖性这种题更多的是树形dp的应用，重点在于理解；
8.总结
1、背包问题是很特殊的一类题，题目的设问往往是问能做到什么的最大值或最小值，各种不同的应用也是分别明显，至于考场可能出现的其他变式也之不过是这01背包的基础上做修改和衍生，重点永远是降低复杂度。