01背包详解包含路径输出

背包问题——“01背包”详解及实现（包含背包中具体物品的求解）分类：背包问题2011-11-2614:419554人阅读评论(10)收藏举报pathtabledelete测试c算法-----EditbyZhuSenlinHDU01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解将那些物品装入背包可使总价值最大。动态规划（DP）：1）子问题定义：F[i][j]表示前i件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。2）根据第i件物品放或不放进行决策(1-1)其中F[i-1][j]表示前i-1件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值；而F[i-1][j-C[i]]+W[i]表示前i-1件物品中选取若干件物品放入剩余空间为j-C[i]的背包中所能取得的最大价值加上第i件物品的价值。根据第i件物品放或是不放确定遍历到第i件物品时的状态F[i][j]。设物品件数为N，背包容量为V，第i件物品体积为C[i]，第i件物品价值为W[i]。由此写出伪代码如下：[cpp]viewplaincopy1.F[0][]←{0}2.3.F[][0]←{0}4.5.fori←1toN6.7.dofork←1toV8.9.F[i][k]←F[i-1][k]10.11.if(k=C[i])12.13.thenF[i][k]←max(F[i][k],F[i-1][k-C[i]]+W[i])14.15.returnF[N][V]以上伪代码数组均为基于1索引，及第一件物品索引为1。时间及空间复杂度均为O(VN)举例：表1-1为一个背包问题数据表，设背包容量为10根据上述解决方法可得到对应的F[i][j]如表1-2所示，最大价值即为F[6][10].表1-1背包问题数据表物品号i123456体积C231465价值W5651197表1-2前i件物品选若干件放入空间为j的背包中得到的最大价值表012345678910000000000000100555555555205661111111111111130551011111616161616405510111116161616175055101111192424293060551011111924242930很多文章讲背包问题时只是把最大价值求出来了，并没有把所选的是哪些物品找出来。本人在学习背包问题之前遇到过很多的类似问题，当时也是只求得了最大价值或最大和，对具体哪些物品或路径等细节也束手无策。再次和大家一起分享细节的求法。根据算法求出的最大价值表本身其实含有位置信息，从F[N][V]逆着走向F[0][0]，设i=N,j=V，如果F[i][j]==F[i-1][j-C[i]]+W[i]说明包里面有第i件物品，同时j-=C[i]，不管F[i][j]与F[i-1][j-C[i]]+W[i]相不相等i都要减1，因为01背包的第i件物品要么放要么不放，不管放还是不放其已经遍历过了，需要继续往下遍历。打印背包内物品的伪代码如下：[cpp]viewplaincopy1.i←N2.3.j←V4.5.while(i0&&j0)6.7.doif(F[i][j]=F[i-1][j-C[i]]+W[i])8.9.thenPrintW[i]10.11.j←j-C[i]12.13.i←i-1当然也可以定义一个二维数组Path[N][V]来存放背包内物品信息，开始时Path[N][V]初始化为0,当F[i][j]==F[i-1][j-C[i]]+W[i]时Path[i][j]置1。最后通过从Path[N+1][V+1]逆着走向Path[0][0]来获取背包内物品。其中Path[0][]与Path[][0]为边界。加入路径信息的伪代码如下：[cpp]viewplaincopy1.F[0][]←{0}2.3.F[][0]←{0}4.5.Path[][]←06.7.fori←1toN8.9.dofork←1toV10.11.F[i][k]←F[i-1][k]12.13.if(k=C[i]&&F[i][k]F[i-1][k-C[i]]+W[i])14.15.thenF[i][k]←F[i-1][k-C[i]]+W[i]16.17.Path[i][k]←118.19.returnF[N][V]andPath[][]打印背包内物品的伪代码如下：[cpp]viewplaincopy1.i←N2.3.j←V4.5.while(i0&&j0)6.7.doif(Path[i][j]=1)8.9.thenPrintW[i]10.11.j←j-C[i]12.13.i←i-1在时间及空间复杂度均为O(NV)的情况下，利用Path[][]的方法明显比直接通过F[i][j]==F[i-1][j-C[i]]+W[i]来打印物品耗费空间，Path[][]需要额外的空间O(NV)但总空间复杂度不变仍为O(NV)。但下面要讲到的O(V)的空间复杂度的方法却不能利用关系式F[j]==F[j-C[i]]+W[i]而只能利用Path[][]进行标记.接下来考虑如何压缩空间，以降低空间复杂度。时间复杂度为O(VN)，空间复杂度将为O（V）观察伪代码可也发现，F[i][j]只与F[i-1][j]和F[i-1][j-C[i]]有关，即只和i-1时刻状态有关，所以我们只需要用一维数组F[]来保存i-1时的状态F[]。假设i-1时刻的F[]为{a0，a1，a2，…，av}，难么i时刻的F[]中第k个应该为max(ak,ak-C[i]+W[i])即max(F[k],F[k-C[i]]+W[i])，这就需要我们遍历V时逆序遍历，这样才能保证求i时刻F[k]时F[k-C[i]]是i-1时刻的值。如果正序遍历则当求F[k]时其前面的F[0],F[1]，…，F[K-1]都已经改变过，里面存的都不是i-1时刻的值，这样求F[k]时利用F[K-C[i]]必定是错的值。最后F[V]即为最大价值。求F[j]的状态方程如下：(1-2)伪代码如下：[cpp]viewplaincopy1.F[]←{0}2.3.fori←1toN4.5.dofork←VtoC[i]6.7.F[k]←max(F[k],F[k-C[i]]+W[i])8.9.returnF[V]同样，怎么求路径？利用前面讲到的Path[][]标记，需空间消耗O(NV)。这里不能用F[j]==F[j-C[i]]+W[i]来判断是因为一维数组并不能提供足够的信息来寻找二维路径。加入路径信息的伪代码如下：[cpp]viewplaincopy1.F[]←{0}2.3.Path[][]←04.5.fori←1toN6.7.dofork←VtoC[i]8.9.if(F[k]F[k-C[i]]+W[i])10.11.thenF[k]←F[k-C[i]]+W[i]12.13.Path[i][k]←114.15.returnF[V]andPath[][]打印路径的伪代码和前面未压缩空间复杂度时的伪代码一样，这里不再重写。下面针对前面提到的表1-1提供两种方法的测试代码：[cpp]viewplaincopy1.#includeiostream2.#includecstring3.#includeCreateArray.h//该头文件用于动态创建及销毁二维数组，读者自己实现4.usingnamespacestd;//时间复杂度O(VN),空间复杂度为O(VN)[cpp]viewplaincopy1.intPackage01(intWeight[],intValue[],intnLen,intnCapacity)2.{3.int**Table=NULL;4.int**Path=NULL;5.CreateTwoDimArray(Table,nLen+1,nCapacity+1);//创建二维数组6.CreateTwoDimArray(Path,nLen+1,nCapacity+1);//创建二维数组7.8.for(inti=1;i=nLen;i++)9.{10.for(intj=1;j=nCapacity;j++)11.{12.Table[i][j]=Table[i-1][j];13.Path[i][j]=0;14.if(j=Weight[i-1]&&Table[i][j]Table[i-1][j-Weight[i-1]]+Value[i-1])15.{16.Table[i][j]=Table[i-1][j-Weight[i-1]]+Value[i-1];17.Path[i][j]=1;18.}19.}20.}21.22.inti=nLen,j=nCapacity;23.while(i0&&j0)24.{25.if(Path[i][j]==1)26.{27.coutWeight[i-1];28.j-=Weight[i-1];29.}30.i--;31.}32.coutendl;33.34.intnRet=Table[nLen][nCapacity];35.DestroyTwoDimArray(Table,nLen+1);//销毁二维数组36.DestroyTwoDimArray(Path,nLen+1);//销毁二维数组37.returnnRet;38.}//时间复杂度O(VN)，不考虑路径空间复杂度为O(V)，考虑路径空间复杂度为O(VN)[cpp]viewplaincopy1.intPackage01_Compress(intWeight[],intValue[],intnLen,intnCapacity)2.{3.int*Table=newint[nCapacity+1];4.memset(Table,0,(nCapacity+1)*sizeof(int));5.int**Path=0;6.CreateTwoDimArray(Path,nLen+1,nCapacity+1);//创建二维数组7.8.for(inti=0;inLen;i++)9.{10.for(intj=nCapacity;j=Weight[i];j--)11.{12.Path[i+1][j]=0;13.if(Table[j]Table[j-Weight[i]]+Value[i])14.{15.Table[j]=Table[j-Weight[i]]+Value[i];16.Path[i+1][j]=1;17.}18.}19.}20.21.inti=nLen,j=nCapacity;22.while(i0&&j0)23.{24.if(Path[i][j]==1)25.{26.coutWeight[i-1];27.j-=Weight[i-1];28.}29.30.i--;31.}32.coutendl;33.34.intnRet=Table[nCapacity];35.DestroyTwoDimArray(Path,nLen+1);//销毁二维数组36.delete[]Table;37.returnnRet;38.}测试代码[cpp]viewplaincopy1.intmain()2.{3.intWeight[]={2,3,1,4,6,5};4.intValue[]={5,6,5,1,19,7};5.intnCapacity=10;6.coutPackage01(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity)endl;7.coutPackage01_Compress(Weight,Value,sizeof(Weight)/sizeof(int),nCapacity)endl;