算法8_回溯法.ppt

1 y[0]=0 y[1]=1 y[1]=0 y[0]=1 y[2]=1 y[3]=1 y[4]=1 y[5]=0 y[6]=0 y[7]=0 1 0 0 0 1 0 1 0 0 0 0 0 y[4]=0 y[3]=0 y[2]=0 1 0 0 0 0 1 0 0 164.67 163.81 (w0,w1,...,w7)=(1,11,21,23,33,43,45,55), (p0,p1,...,p7)=(11,21,31,33,43,53,55,65), M=110。 bp=cp+rp =p0*1+p1*1+p2*1+p3*1+p4*1+p5*0+p6*0+p7/w7*(110-89) =(11+21+31+33+43)+65/55*21 =139+24.81 =163.81 为当前结点X的上界函数值。若bp当前最优解值下界估计值L，则可断定X子树上不含最优答案结点，可以剪去以X为根的子树。 1 y[0]=0 y[1]=1 y[1]=0 y[0]=1 y[2]=1 y[3]=1 y[4]=1 y[5]=0 y[6]=0 y[7]=0 1 0 0 0 1 0 1 0 0 0 0 0 y[4]=0 y[3]=0 y[2]=0 1 0 0 0 0 1 0 0 164.67 163.81 139 L=139 若得到必威体育精装版可行解（到达状态空间树的第n+1层），则更新当前最优解下界值L。 164.67 163.81 139 L=139 向左走：更新 值，bp值不变。用约束函数 剪去不含可行解的分枝； 向右走：更新bp的值， 值不变。用限界函数bp≤L剪去不含最优解的分枝。 162.44 162 149 161.64 151 L=149 L=151 159.78 96 159 L=159 160.18 160.22 159.77 158 157.56 159.33 157.64 159.77 157.11 154.89 157.44 155.12 y[4]=1 1 y[0]=0 y[1]=1 y[1]=0 y[0]=1 y[2]=1 y[3]=1 y[5]=0 y[6]=0 y[7]=0 1 0 0 0 1 0 1 0 0 0 0 0 y[4]=0 y[3]=0 y[2]=0 1 0 0 0 0 1 0 0 0-1背包问题算法实现 程序8-8 背包类Knapsack template class T class Knapsack { public: T BKnapsack(int *x); protected: void BKnapsack(int k,T cp,T cw,T fp,int *x,int *y); T Bound(int k,T cp,T cw); //Bound为上界函数bp T m,*w,*p; //已按p[i]/w[i]≥p[i+1]/w[i+1]排序 int n; }； 背包载重 物品个数 当前最大收益(下界函数L值) 存入x中,保存当前最优可行解 k是当前待考察的物品编号； （0≤k≤n-1） cp是当前收益； cw是当前背包重量。 程序8-8 上界函数Bound template class T T KnapsackT::Bound(int k,T cp,T cw) //向右走（xk=0时）调用Bound函数重新计算bp值 { //向左走（xk=1时），收益上界值bp不变，无需重新计算； //向右走（xk=0时），收益上界值bp会变，因此需要重新计算。 //若新的bp值＜当前最优解下界fp，则对右孩子剪枝，不生成右子树。 //cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 T b=cp,c=cw; //当前收益cp和当前背包重量cw不变（xk=0） for (int i=k+1;in;i++) //对剩余物品求一般背包问题的解 { c+=w[i]; if (cm) b+=p[i]; //第i个物品可以全部放入 else return (b+(1-(c-m)/w[i])*p[i]);//第i个物品只能放部分 } return b; } 程序8-8 背包类 (物品已按p[i]/w[i]≥p[i+1]/w[i+1]排好序） template class T void KnapsackT::BKnapsack(int k,T cp,T cw,T fp,int *x,int *y) { //cp是当前收益，cw是当前背包重量，k是当前待考察的物品编号 //fp是当前最大收益 //考