一.0/1背包

　　题目链接：

　　因为二维数组的动规维护极其简单，这里就不再详述了。

　　二维数组降低空间开销的方法是使用滚动数组，可以将空间复杂度从O(nm)降低为O(m)，此处也不赘述。

　　直接讲讲一维数组维护的思路：

　　先看二维数组动规的状态转移方程：

　　F[i,j]=max{F[i-1,j],F[i-1,j-Vi]+Wi(if j>=Vi)}

　　边界：F[0,0]=0；目标：F[n][m]

　　我们发现，对于每一层i，数组的维护过程中仅是j的值在改变，故可以直接将数组的第一维省略。

　　那么状态转移方程就变成：F[j]=max{F[j-Vi]+Wi(if j>=Vi)}

　　但这里有一个注意点，就是循环的顺序问题。第一层i的1~n循环自然没问题，主要是第二层的j，必须是采用倒序循环m~V[i]。

　　原因是F[j]的值是与F[j-Vi]有关的，若采用正序循环，那么在更新到这一层的F[j]时，所关心的F[j-Vi]已经是这一层的了，而不是上面二维中所需的第i-1层（也就是上一层）了。

　　代码实现如下：时间复杂度O(nm)

　　事先说明一下：本文所有代码中的读取均使用快读，下面先贴一下快读代码：

inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    return x*f;}int zero_one_knapsack()  // 0/1背包{    int const N = 1000+10;    int v[N],w[N],f[N];    memset(f,0,sizeof(f));        int n=read(),m=read();    for(int i=1;i<=n;i++)v[i]=read(),w[i]=read();        for(int i=1;i<=n;i++)        for(int j=m;j>=v[i];j--)            f[j]=max(f[j],f[j-v[i]]+w[i]);            return f[m];}

 

二.完全背包

　　题目链接：

　　类似于0/1背包，当采用正序循环时，每种物品就可以使用无限次了。

　　话不多说，直接上代码：

int full_knapsack()  // 完全背包{    int const N = 1000+10;    int v[N],w[N],f[N];    memset(f,0,sizeof(f));        int n=read(),m=read();    for(int i=1;i<=n;i++)v[i]=read(),w[i]=read();        for(int i=1;i<=n;i++)        for(int j=v[i];j<=m;j++)            f[j]=max(f[j],f[j-v[i]]+w[i]);            return f[m];}

 

三.多重背包

　　题目链接：

　　最直接的方法是把第i种物品看成独立的Si个物品，转化为共有ΣCi(i=1~n)个物品的0/1背包问题进行计算，时间复杂度O(M*ΣCi)。

　　这种方法把每种物品拆成了Si个，效率较低。

　　代码如下：

int multiple_knapsack_i()  // 多重背包I{    int const N = 1000+10;    int v[N],w[N],s[N],f[N];    memset(f,0,sizeof(f));        int n=read(),m=read();    for(int i=1;i<=n;i++)v[i]=read(),w[i]=read(),s[i]=read();        for(int i=1;i<=n;i++)        for(int j=1;j<=s[i];j++)            for(int k=m;k>=v[i];k--)                f[k]=max(f[k],f[k-v[i]]+w[i]);                return f[m];}

　　下面介绍二进制优化算法：

　　众所周知，任何整数都可以表示为若干个2的整数次幂相加。所以我们可以将每种物品的Si个打包成若干组，每一组的数量取值为：1,2,4,8，…，2^k-1,sum；sum的作用是使得这组数的和的最大值恰好为Si。

　　那么就可以把每种物品分成log₂Si个，效率较高。

　　代码如下：

int multiple_knapsack_ii()  // 多重背包II  二进制优化{    int const N = 1010*11, M = 2010;    int v[N],w[N],f[M];    memset(f,0,sizeof(f));        int n=read(),m=read();    int cnt=0;    for(int i=1;i<=n;i++)    {        int a=read(),b=read(),s=read(),k=1;        while(k<=s)        {            v[++cnt]=a*k;            w[cnt]=b*k;            s-=k;k<<=1;        }        if(s)        {            v[++cnt]=a*s;            w[cnt]=b*s;        }    }    for(int i=1;i<=cnt;i++)        for(int j=m;j>=v[i];j--)            f[j]=max(f[j],f[j-v[i]]+w[i]);            return f[m];}

 

四.分组背包

　　题目链接：　　

　　有了上面几个背包模型，分组背包也是极其简单，但有几个注意点。

　　首先是倒序循环，其次，对于每一组内Si个物品的枚举，k应放在j的内层，这是因为每一组内至多选择一个物品，若把k至于j的外层，就会在F数组的转移上产生累积，最终会选择超过1个物品。

　　从动规的角度看，i是“阶段”，i与j共同构成“状态”，而k是“决策”，在第i组内选择哪个物品，这三者的顺序绝对不能混淆。

　　代码如下：

int grouping_knapsack(){    int const N = 1000+10;    int v[N][N],w[N][N],s[N],f[N];    memset(f,0,sizeof(f));        int n=read(),m=read();    for(int i=1;i<=n;i++)    {        s[i]=read();        for(int j=1;j<=s[i];j++)            v[i][j]=read(),w[i][j]=read();    }    for(int i=1;i<=n;i++)        for(int j=m;j>=0;j--)            for(int k=1;k<=s[i];k++)                if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);                return f[m];}

 

　　最后说一句，动规思想解决背包问题最需要注意的就是循环的嵌套，必须要以物品->体积->决策的顺序。