4回溯法(4)

0-1背包问题0/1背包问题的描述如下：已知有一个可容纳重量为M的背包以及n种物品，其中第i件物品的重量为wi，每件物品的单位效益是pi(pi0)。我们要从这n个物品中选出一部分，使得Mxwniii1并且使得niiixp1极大化。那么这n件物品的选取状态就构成一个取0或者1的解向量。这个问题的解向量可以用一个n元组(x1,x2,x3,…,xn)来表示，其中xi表示第i件物品的选取状态，若第i件物品被选中，则xi=1,否则xi=0。所以问题的解空间就有2n个不同的n元组组成。假设有3种物品即n=3，那么此0/1背包问题的解空间就是：{(0,0,0),(0,0,1),(0,1,1),(1,0,1),(0,1,0),(1,0,0),(1,1,0),(1,1，1)}。构造问题的状态空间树如图4-14。图4-14n=3的0-1背包问题的状态空间树状态空间树中从第i层到第i+1层的边上的值给出了解向量中xi的值。从树的根结点到任意叶结点的路径就是一个可能的解向量。例如从根结点到最右端的叶结点的路径就对应于解空间中的元素(0,0,0)。可以将上面的问题进一步具体化。已知物品的数量n=3,(w1,w2,w3)=(16,15,15)，(p1,p2,p3)=(45,25,25)，M=30。那么从图4-14的根结点开始检索。根结点1是唯一的活结点，也是当前的E-结点。假设先生成根结点1的儿子结点2，那么结点2也成为活结点，并且结点2成为当前的E-结点。这时说明选取了物品1，那么背包里面的容量就只剩下30-16=14，当前获得的效益值是p1=45。当从结点2生成其儿子结点4时，我们会发现背包的容量14小于物品2的重量15，所以结点4导致一个当前条件下的不可行解。那么可以删除以结点4为根的子树，并且返回结点2，生成其儿子结点5，即不选取物品2。此时结点5就成为当前E-结点。当生成结点5的儿子结点10时，导致一个不可行解。所以返回结点5并生成它的儿子结点11，11是叶结点且可行。这时就得到一个可行解，这个可行解由根结点1到叶结点11的路径确定即(x1,x2,x3)=(1,0,0)。反复使用此方法，直到检索完整个解空间为止。然后将得到的所有可行解进行比较，得最优解。0/1背包问题的限界函数应该能产生某些值的上界，从而可以使某些不符合的活结点成为死结点。假设在所求问题的状态空间树的结点T处(T处于树中的第k+1层)确定了xi的值，其中1≤i≤k。那么结点T的上界可以这样计算，对于k+1≤i≤n，用贪心算法处理剩余的xi。简单的说，就是将剩余的物品按照它们的单位效益值排序，然后依次将物品装入背包，到无法完全装入下一个物品时，可以将该物品的一部分装满背包，这样就得到一个上界。可以假设P是当前的效益总值，W是当前背包的重量，restP是当前还没有考虑的物品的效益总值，bestP是此前的到的最优值。可知，当P+restP≤bestP时，可以杀死要考虑的活结点。那么，用函数Bound()来确定以结点T为根结点的子树中可能解的上界,其中用全局数组w[n]存储物品的重量，p[i]存储物品的效益值；参数kiiixpP1，即当前的总效益值；参数kiiixwW1，即当前背包中物品的总重量。k是上一个考虑了的物品；全局变量M是背包的容量，n是物品的个数。进入函数前，假设有1/1/iwipiwip，1=i=n，并且，算法的输入为当前总效益值P，当前背包总重量W，要考虑的物品的序号k，背包容量M；输出为当前结点所能得到的效益值上界Bound()的代码描述：ElemtypePBound(ElemtypePP,ElemtypeWW,intk,intM)1b←P;//变量b用来存储改变的总效益值,其初始值为P；2c←W;//变量c用来存储改变后的背包重量，其初始值为W；3fori←k+1ton//逐一考虑k之后的物品；4do{5c←c+w[i];//物品i放入背包，背包重量加上w[i]；6ifcM//背包没有超重，总效益值增加p[i]；7thenb←b+p[i];8elsereturn(b+p[i]/w[i]*(M–c+w[i]));9//背包超重，将此时算出的总效益值作为一个上界返回；10}11returnb;//物品可以全部装入背包，将所有物品的总效益值作为上界返回；由这个函数的实现可以看出，问题的状态空间树的结点T的左儿子结点与结点T本身具有相同的上界。所以当从状态空间树的一个结点生成它的左儿子结点时，不用调用限界函数Bound()。只要结点的左儿子结点是一个可行结点，就检索其左子树。那么只有在可行的左儿子结点都被检索之后，才需要调用函数Bound()。当给出了Bound()函数之后，就可以实现求解0/1背包问题的回溯算法。用迭代的回溯方法求解0/1背包问题算法如下，其中假设有n种物品，背包的容量是M。我们用数组p[n]存放物品的效益值，用数组w[n]存放物品的重量。根据前提条件物品按照1/1/iwipiwip，1=i=n的顺序排放。参数wEnd是背包的最后重量，pMax是最大效益值。数组x[n]表示物品的解向量，若物品放入背包则x[i]=1,否则x[i]=0。变量wn是背包当前重量，pn是背包中装入的物品当前取得的总效益值。数组y[n]储存的是到当前结点的路径。算法的输入为背包容量M，物品数n，各个物品的效益值，重量；输出为0/1背包问题的一个解向量0/1背包问题的回溯算法BKnap1描述：intBKnap1(intM,intn,ElemtypePp[],ElemtypeWw[],boolx[],ElemtypePpMax,ElemtypeWwEnd)1pn←0;//pn用来存储当前获得的总效益值；2wn←0;//wn用来存储前背包重量；3k←1;4pMax←-1;//最大效益值初始化为-1;5whileTRUE6do{7whilek≤nandwn+w[k]≤M8do{//还有没考虑的物品，且背包有足够容量，则将此物品加入背包；9wn←wn+w[k];//改变背包重量；10pn←pn+p[k];//改变当前获得的总效益值；11y[k]←1;//标志物品k放入背包；12k←k+1;13}14ifkn15then{//所有物品都装入背包，那么已经求出问题的解；16pMax←pn;17wEnd←wn;18forj←1ton//将问题的解赋给数组x[n]；19dox[j]←y[j];20}21elsey[k]←0;//物品k不能全部装入背包22whileBound(pn,pw,k,M)≤pMax23do{//新的上界比当前最大效益值要小；24whilek≠0andy[k]≠125dok←k–1;//找到当前背包中最后放入的物品；26ifk=0//条件成立时，算法在此处结束；27thenreturn0;28y[k]←0;//将物品k从背包中取出29wn←wn–w[k];30pn←pn–p[k];31}32k←k+1;//考虑下一个物品。33}当pMax的的值不是-1时，可知niixippMax1。在第12行到第18行的while循环中，算法BKnap1一直在生成一连串可行的左儿子结点。因为数组y[i](1≤i≤k)储存的是到当前结点的路径，所以可得当前背包重量11kiiyiwwn以及当前背包的效益值11kiiyippn。执行完这个循环以后，对k的值进行判断。如果kn，可以推出pnpMax。因为根据限界函数的作用，如果有pn≤pMax的话，限界函数是会杀死到此叶结点的路径上的某一结点，从而导致无法到达这一叶结点。如果k=n，则说明w[k]的值大于背包中剩余空间的值，所以必须产生当前E-结点的右儿子。此时调用限界函数Bound()得到一个上界值。如果这个上界值比pMax小(即Bound(pn,pw,k,M)≤pMax)，那么说明当前最优解要比当前正在考虑的路径所能导出的解要好，所以这条路径可以及时的被终止。在调用Bound()函数之后的while循环中，沿着最近的结点进行回溯，一直回溯到没有结点可以回溯或者当前回溯到的结点可以生成右儿子为止。如果找不到这样的结点，那么算法就此结束。如果有，则处理这个结点的右儿子。如此往复直至算法结束。在Bknap1算法中的第7行到第13行的while循环所实现的功能，其实在Bound()函数中已经基本实现了，所以可以对这两个算法做进一步的改进。通过对Bound()函数做一定的修改来代替BKnap1算法中7到13行的while循环所实现的功能。这个修改后的Bound()函数叫做有边界效应的限界函数。其中参数bp表示改变后的总效益值，cw表示改变后的总重量。数组y[n]在调用此函数之前已经被定义。算法的输入包括当前总效益值，当前背包总重量，要考虑的物品的序号k，背包容量M，刚移到的左儿子对应的效益值，重量，以及上一个不适合的物品；输出为当前结点所能得到的效益值上界。有边界效应的边界函数Bound()的代码描述:ElemtypePBoundN(ElemtypePP,ElemtypeWW,ElemtypePbp,ElemtypeWcw,intk,intM,inti)1bp←p;2cw←w;3fori←k+1ton//逐一考虑k之后的物品；4do{5if(cw+w[i])≤M//没有超过背包容量M；6then{7cw←cw+w[i];//改变背包重量；8bp←bp+p[i];//改变当前总效益值；9y[i]←1;//将物品i放入背包；10}11elsereturn(bp+p[i]/w[i]*(M–cw));12}13returnbp;//物品可全装入背包，将所有物品的总效益值作为一个上界返回；那么相应的求解0/1背包问题的算法也要改进。改进的求0-1背包问题的算法的代码描述：intBKnapN(intM,intn,ElemtypePp[],ElemtypeWw[],boolx[],ElemtypePpMax,ElemtypeWwEnd)1pn←0;//pn用来存储当前获得的总效益值2wn←0;//wn用来存储当前背包的重量3k←0;4pMax←-1;5whileTRUE6do{7whileBound(pn,pw,bp,cw,k,M,j)≤pMax8do{//计算出来的新的上界比当前最大效益值要小；9while(k≠0)&&y[k]≠110dok←k–1;//反过头寻找当前背包中最后放入的物品；11ifk=0//若此条件成立，算法在此处结束；12thenreturn0;13y[k]←0;//将物品k从背包中取出，并改变当前背包14wn←wn–w[k];//量和背包中物品的总效益值；15pn←pn–p[k];16}17pn←bp;//下三行的作用等价于BKnap1算法中12行到18行的//while循环的作用；18wn←cw;19k←j;20ifkn21then{//所有的物品都可装入背包，已经是一最优解，得到其效益最22pMax←pn;//值和背包中的最终重量；23wEnd←wn;24forj←1ton;j++)25dox[j]←y[j];//将问题的解赋给数组x[n]；26}27else//物品k不能全部装入背包28y[k]←0;29}下面通过一道例题来了解两个限界函数的差异。例4-4有一个背包问题描述如下：物品数n=8，背包的容量M=110,各个物品的效益值(p1，p2，p3，p4，p5，p6，p7，p8)=(11，21，31，33，43，53，55，65)，各个物品的重量(w1，w2，w3，w4，w5，w6，w7，w8)=(1，11，21，23，33，43，45，55)。首先根据BKnap1算法来构造求解过程中产生的树。如图4-15.11112325356568108336356966610610915964891391011513991492100000164.88Y1=10Y2=10Y3=10Y4=110159