[数据结构与算法]【动态规划思想之背包基础四讲】

???? 接下来我的文章将会重点关注于动态规划，包括一些基础模型的知识点讲解。相关专题的竞赛题，leetcode的刷题笔记将会很快更新在刷题专栏里。

???? 这一次我们把01背包，多重背包，完全背包，分组背包讲个透

目录

???? 01背包

???? 完全背包

???? 多重背包

???? 分组背包

???? 01背包

?先来看一个01背包经典模型

给定N个物品，其中第i个物品的体积为Vi ,价值为Wi 。有一个容积为m的背包，要求选择一些物品放入背包，使得物品总体积不超过m的前提下，物品的价值总和最大。

?我们先来看一下思路：对于动态规划问题，我们最重要的是要写出他的状态转移方程，也就是说，在当前题干所要求的结果我们不能一步求出的情况下，我们不和他硬刚，而是把它转化成与他相关的别的状态来求解。

比如这个01背包问题里，假设二维数组 f[i][j] 表示的是对于前 i 个物品我们把他放入容积为 j 的背包里可以得到的最大价值是多少，也就是说对于本题而言，f[N][m]就是我们要求的最终结果。最常用的状态转移方程就是：

如果不理解没关系，先用纸记下来，以便于后面讲解的时候对着看。

?我们以4个物品装入容积为10的背包为例子（请把这些参数记在纸上往下对着看）

为了理解上面的状态转移方程，我们采用表格的方式进一步理解，在我看来表格懂了，就全懂了。

我们以前i个物体为行，容积从1到m为列可得表格

现在我们看到的就是f[i][j]画成表格并且初始化之后的样子，如表格初始化所示，f[0][j]表示把前0个物品放入容积为j的背包中的最大价值，很显然在没东西放的时候最大价值只能是0,所以我们看到有一行的值全是0。同理，f[i][0]表示的就是对于前i个物品放入容积为0的背包时候最大价值是多少，这个也很显然，没地方放那么最大价值也只能是0，所以有一列的值全是0。现在我们来考虑一下其他空着的地方应该怎么填，我们还需要知道我们表格的最右下角的值就是我们题干的结果，也就是f[4][10].

??????????????????

?现在我们这个表格从f[1][1]开始往右填，由于前一个物品选一个出来放入背包本质就是这第一个物品放或者不放，所以当容积小于3的时候放入的最大价值是0，因为第一个物品的容积是3.所以我们快速填满这一行后面的表格。很显然在前一个物品里选一个物品放入容积大于等于3的背包最大价值只能是4.

从这里开始我们正式进入状态方程的解释环节，当从前i个物品里选,其中i>=2时，我们把i=2这一行的表格填满如图。

这里我们一定要先理解状态转移方程：对于第i个物品，我们每次把前i个物品放入背包的时候,其实只有两种状态，也就是第i个物品要么放，要么不放，就只有这两种状态！那么到底要取哪一个状态呢？其实答案很简单，如果选择不放第i个物品但背包可以获得最大价值，也就是说在前i-1个物品里面选物品放入背包的价值最大，那就选择不放；一样的，如果背包容积大于等于第i个物品的容积，也就是说第i个物品可以放进去的前提下，如果放入第i个物品可以获得最大价值，那么就选择放进去。我们每次比较这两个看看哪一个更大就填入表内。这便是上面状态转移方程的含义。

再回到我们的表格，对上面这段描述如果理解了的话，接下来就很简单了。举个例子：先看f[2][3],在状态转移方程中，这表示在前2个物品中选出物品放入容积为3的背包使得价值最大。由我们上面的分析可知，那么第2个物品可选或不选，但因为第二个物品体积为4，不可以放入容积为3的背包中，所以只能不选，那么既然第二个物品不能放进去，那意思是不是就和把前一个物品放入容积为3的背包所获得的价值是一样的。也就是说f[2][3]与f[1][3]是完全一样且相等的。继续看例子：再来看f[2][4]，一样的，我们考虑此时第二个物品放入或不放，放入的话刚好能装满容积为4的背包，且价值为5，如果不放入的话那么和上一个例子一样f[2][4]=f[1][4]=4，所以我们选择把第二个物品放入背包。最后看一个例子：把前面两个例子看懂后，我们继续看f[2][5]，一样的我们如果不放入第二个物品那么最大价值就是f[2][5]=f[1][5]=4，如果放入的话，此时价值为5，可是背包容积还剩1没放，于是我们再回去看f[1][1]是多少，也就是对应于状态转移方程中的下面那一行即：

f[2][5]=f[1][5-4]+5 :我们选择把第二个物品放进去后，背包最大价值就变成了f[1][1]加上第二个物品的价值5.又因为f[1][1]=0，所以最大价值应该是5.这便是状态转移方程的全部理解。

所以我们在回去看状态转移方程，其实每次求一个格子都只和 i-1 的状态有关对吧。前面这三个例子其实就是状态转移方程本身。知道了这些原理之后，后面的格子请读者们自行推导，换汤不换药。

二维数组做法的c++代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9999;
int f[N][N];  /*f[i][j]表示从前i个物品中选出物品放入容积为j的背包中的最大价值*/
int v[N],w[N];  /*v[i],w[i]分别表示第i个物品的体积和价值*/
int main()
{ 
  int m,n;
  cin>>m>>n;  /*输入物品个数m和背包容积n*/
  for(int i=1;i<=m;i++)  cin>>v[i]>>w[i]; /*输入每个物品的体积和价值*/
  for(int i=1;j<=m;i++) /*外层循环为物品的循环*/
     for(int j=1;j<=n;j++)  /*内层循环为背包容积的循环，从1~n*/
         f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); /*接下来便是状态转移方程啦*/
printf("%d",f[m][n]); /*打印最终结果*/
return 0;
}

• 01背包的一维优化?

懂得了二维数组的做法，我们可以发现，其实二维数组的做法是十分浪费空间的。原因就在于在第i个物品的时候，假如第i个物品的体积v[i] 小于当前循环到的背包容积j的话，那么实际上这时候f[i][j]总是等于f[i-1][j]的（根据状态转移方程），也就是说我们完全是将上一行中的前几个数字复制粘贴过来到第i行来的，是完全没必要的操作。

假设一维数组f[N]表示

一维数组用我们刚刚的二维数组去解释其实就是下一行的数值去更新第一行的数值，也就是说每次开启新一轮的 i 循环的时候，其实此时这个一维数组里存的就是我们上一行的数据，在一维数组里就不存在把上一行数据复制过来的无聊操作了，因为它是以不动的方式去处理这些数据的。

我们以上面那个二维数组举例，现在我们看到的是一个循环到 i=1的一维数组（红色部分表示i=1行的数据，蓝色部分表示i=2行的数据）：

?我们用倒序的方法，先求f[10],数据就变成了：

?这里我们分析一下这f[10]对应的其实就是二维数组里的f[2][10],那么他是怎么求的呢？我们在二维数组里就说过，求第i层的数只和i-1层有关，所以我们可以发现，我们红色部分表示的就是i-1层的数据，f[10]其实就是由前面红色部分(i-1层的数据)求出来的，先和f[j]比较，也就是对应于二维数组里的f[i-1][j]，看看哪一个更大就把哪个更新给蓝色方块。红色部分和i-1层是一个意思！！！f[10]=f[10-v[i] ]+w[i];这便是一维数组形式的状态转移方程.

一维写法本质和二维是相同的，所以状态转移方程也十分地相似。

贴上c++的一维数组代码：

#include<iostream>
#include<algorithm>
const int N=999999;
int f[N];
int v[N],w[N];
int main()
{
cin>>m>>n; /*输入物品个数和背包容积*/
for(int i=1;i<=m;i++)  cin>>v[i]>>w[i]; /*输入背包的体积和价值*/
for(int i=1;i<=m;i++)  
  for(int j=n;j>=v[i];j--)  /*一维数组倒序循环*/
    f[j]=max[f[j],f[j-v[i]]+w[i]);  /*一维数组的状态转移方程*/
return 0;    
}

这里需要解释一下为什么需要倒序，这里涉及到接下来的完全背包问题，如果正序写法其实就是完全背包而不是01背包了。这里我们只做普通解释。我们f[j]的值是由前面的红色部分得出来的，想象一下，如果我们正序的话，那么前面红色部分是不是就会被改变了，那后面的值既然是依赖着前面的值求出来的，前面的值改变了后面的值还怎么求出来呢？求出来的这个值就肯定不是我们想要的值了。

???? 完全背包

完全背包与01背包十分地类似，01背包是每个物品只能选一次，而完全背包是每个物品选的个数不限，求能放入的最大价值是多少。

完全背包典型模型：

给定n种物品，其中第i种物品的体积为vi ,价值为wi，并且有无数个。有一容积为m的背包，要求选择若干个物品放入背包，使得物品总体积不超过m的前提下，物品的价值总和最大。

理解了01背包的一维数组问题，我们直接上手完全背包的一维数组写法。 我们知道，在01背包里面，每一个状态都只能由i-1层的状态求出来，这是因为01背包里面每一个物品只能取一次。在01背包的一维写法里面，我们内层循环如果采用了正序写法，思考一下会发生？那么我们红色的部分将会从头开始改变，并且每一个红色的部分代表的意思都是至少放入了1个第i个物品。比如：当我们容积循环到j-v[i]的时候放入了一次 i 物品，当我们容积循环到 j 的时候，可能又要再次放入 i 物品，具体表现在此时的f[j-v[i]]+w[i]赋值给了f[j]。

也就是说，正因为正序，所以值从前面开始变，而后面的值又必须依赖前面的值，所以即使前面格子已经放入了至少一个 i 物品，因为它依赖于前面的格子，所以他如果选择放入i 后第 j-v[i]个格子可能正是之前放过至少一个物品的格子。这样就实现了可能同一个物品放很多次并且背包总是最大价值的情况。

完全背包的一维数组c++代码实现如下(其实就是01背包内层循环倒序写）：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9999999;
int f[N];  /*f[j]表示从前i个物品中取出物品放入容积为j的背包中所能放入的最大价值*/
int v[N],w[N];  /*分别表示第i个物品的体积和价值*/
int main()
{
  int m,n; /* m表示物品的个数,n表示目标背包的容积*/
   cin>>m>>n;
   for(int i=1;i<=m;i++) cin>>v[i]>>w[i]; /*输入物品的体积和价值*/
   for(int i=1;i<=m;i++)
      for(int j=v[i];j<=n;j++) /*从v[i]，能放入背包开始循环，否则从1开始如果物品放不入背包也是白循环*/
        f[j]=max(f[j],f[j-v[i]]+w[i])  /*状态转移方程，比较放入或不放入该物品哪个更大后赋值*/
   return 0;
}
          

???? 多重背包

多重背包本质可以写成一个01背包的模型，先来看典型模型：

给定n种物品，其中第 i 种物品的体积为vi，价值为wi，并且有ci个。有一容积为m的背包，要求选择若干个物品放入背包，使得物品总体积不超过m的前提下，物品的价值总和最大

多重背包和01背包类似的地方就是物品的个数都是有限的，所以我们有这么一种解题思路，那就是把ci个物品i平铺展开来，这样问题就变成了01背包，因为他们的个数都是有限的，所以这是一种实现方法 ：

c++代码实现如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9999999;
int f[N];
int v[N],w[N],c[N];
int main()
{
  int m,n;  /*物品的个数和背包容积*/
  cin>>m>>n;
   for(int i=1;i<=m;i++)  cin>>c[i];
   for(int i=1;i<=m;i++)
    for(int k=1;k<=c[i];k++)  /*物品个数的循环，把物品平铺开来*/
      for(int j=m;j>=v[i];j--)   /*01背包的容积层循环*/
          f[j]=max(f[j],f[j-v[i]]+w[i]);  /*状态转移方程*/
   return 0;
}

?我们可以看到，这里有三层嵌套的循环，时间复杂度想必是十分的高的，探究一下可能会超时的原因，正是因为选择了最笨的方法，那就是把物体平铺开来了，物体有多少个就要平铺多少个，导致对比的次数增多了，那么有没有别的方法，能够让我们不用全部平铺开来就可以表示所有的可能的容积情况呢。

先来看看二进制拆分法的原理：对于任何一个整数，我们可以使用二进制拆分的形式将一个整数分解成几个数，这几个数具有这个特征：那就是用这这几个数可以表示出0~这个整数之间的任何数，比如分解一个整数70和90 先根据二进制从2的0次方开始分解 ，可以分解成这样

?

比如我们物品i 一共有70个，分解成二进制形式后，想要表示出放入29个物品i，就可以用2的0次方+2的2次方+2的3次方+2的四次方来表示 ；相当于本来需要循环0~70，我们现在只需要循环将70分解后的7个数，也就是说这时候这7个数分别乘以体积和质量就变成了全新的物品i ，想要表示出选15个放入就是不选2的1次方 ，将2的四次方之前的数全都放入背包，所以我们可以通过这种方法表示出0~70之间的所有数而不用循环70遍。

所以，原本有70个物品的体积为1的物品不需要再摊开70个了，只需要摊开7个就足够了，此时f[j]表示的就是容积为j的情况下能放入的最大价值。

我们可以理解到：严格意义上讲，这次的01背包更新值的时候比较的不是放不放入新的第i个物品的最大价值。我们应该把放不放入新的第i个物品理解成放入不同数量原本的i物品之间的的最大价值之间的比较，这才是二进制拆分法解此模型的本质

c++代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9999999;
int f[N];  /*f[j]表示放入容积为j能放入的最大价值*/
int v[N],w[N]; /*分别表示第i个新物品的体积，质量*/
cnt=0;  /*cnt表示新组成的01背包里面的物品*/
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++)
 {  int a,b,c;  /*a,b,c分别代表第i个物品的体积，质量，个数*/
    cin>>a>>b>>c;
    int k=1;   /*k用来表示二进制的指数，也就是个数*/
    cnt=0;     /*每换一个旧物品都要把cnt的值更新为0*/
    while(k<=c)  /*当抽出来组成新物品的i的个数少于C个数的时候*/
    {  
      cnt++;     
      v[cnt]=k*a;   /*将二进制个数个旧物品组成的物品的体积放入背包*/
      w[cnt]=k*b;   /*将二进制个数个旧物品组成的物品的质量放入背包*/
      cnt++;       
      c-=k;         /*c表示旧的第i个物品剩余个数*/
      k*=2;         /*判断下一个二进制组成的新物品所需的旧物品的个数是否超过剩余的旧物品个数c*/
    }
    if(c>0)   /*当最后一个二进制组成的新物品所需的物品数超过剩余的旧物品个数时候，对于剩余的旧物品不再采取二进制组成新物品，而是直接用剩余的个数组成新物品*/
    {
      cnt++;
      v[cnt]=c*a;
      w[cnt]=c*b;
    }
  }
    for(int i=1;i<=m;i++)     
      for(int j=m;j>=v[i];j--)
         f[j]=max(f[j],f[j-v[i]]+w[i]); /*01背包状态转移方程*/
     return 0;
  }
  


      

???? 分组背包

依旧先来看一下分组背包典型模型，总体来说分组背包算是01背包的变形，算是简单的一种：

给定n组物品，其中第i组有ci个物品。第i组的第j个物品的体积为vij ，价值为wij。有一容积为m的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过m的前提下，物品的价值总和最大。

?分组背包的本质还是01背包，他是怎么用01背包解决这个问题的呢？分组背包和01背包有什么区别呢？我们回到01背包时候写过的二维表格，我们每次放入格子的时候比较的都是一个物品放不放入所能取得的最大价值，但是分组背包一组里有ci个物品并且每组只能取一个。现在我们就很清楚了，原本外层循环i是所有物品的循环，现在的外层循环变成了所有组的循环而不再是单个物品，我们每次打算更新格子的时候，也不再是只比较放不放入一个物品，而是比较ci个物品，把他们依次放入比较，看看谁放入获得的总价值更大，就把这一组的这个物品放进去。

c++代码实现如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9999999;
int f[N];  /*
int v[N][N],w[N][N],c[N];
int main()
{  
   int m,n;
   for(int i=1;i<=m;i++)
    { 
       int g;cin>>g;c[i]=g;
       for(int j=1;j<=c[i];j++)
           cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=m;i++)
      for(int j=n;j>=0;j--)
         for(int k=1;k<=c[i];k++)
           if(j>=v[i][k])
           f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
     return 0;
}