0029算法笔记【回溯法】n后问题和0-1背包问题

1、n后问题问题描述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。问题解析：用n元数组x[1:n]表示n后问题的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。如果将n*n的棋盘看做是二维方阵，其行号从上到下，列号从左到右依次编号为1,2，……n。设两个皇后的坐标分别为(i,j)和(k,l)。若两个皇后在同一斜线上，那么这两个皇后的坐标连成的线为1或者-1。因此有：由此约束条件剪去不满足行、列和斜线约束的子树。程序的递归回溯实现如下：[cpp]viewplaincopy1.//n后问题回溯法计算递归2.#includestdafx.h3.#includeiostream4.#includemath.h5.usingnamespacestd;6.7.classQueen8.{9.friendintnQueen(int);10.private:11.boolPlace(intk);12.voidBacktrack(intt);13.intn,//皇后个数14.*x;//当前解15.longsum;//当前已找到的可行方案数16.};17.18.intmain()19.{20.intn=4,m;21.coutn皇后问题的解为：endl;22.m=nQueen(n);23.coutn皇后问题共有;24.coutm个不同的解!endl;25.return0;26.}27.28.boolQueen::Place(intk)29.{30.for(intj=1;jk;j++)31.{32.if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))33.{34.returnfalse;35.}36.}37.returntrue;38.}39.40.voidQueen::Backtrack(intt)//t扩展的是行41.{42.if(tn)43.{44.sum++;45.for(inti=1;i=n;i++)46.{47.coutx[i];48.}49.coutendl;50.}51.else52.{53.//探索第t行的每一列是否有元素满足要求54.for(inti=1;i=n;i++)55.{56.x[t]=i;57.if(Place(t))58.{59.Backtrack(t+1);60.}61.}62.}63.}64.65.intnQueen(intn)66.{67.QueenX;68.X.n=n;69.X.sum=0;70.71.int*p=newint[n+1];72.73.for(inti=0;i=n;i++)74.{75.p[i]=0;76.}77.78.X.x=p;79.X.Backtrack(1);80.81.delete[]p;82.returnX.sum;83.}数组x记录了解空间树中从根到当前扩展节点的路径，这些信息包含了回溯法在回溯是所需要的信息。利用数组x所含的信息，可将上述回溯法表示成非递归的形式。进一步省去O(n)递归栈空间。迭代实现的n后问题具体代码如下：[cpp]viewplaincopy1.//n后问题回溯法计算迭代2.#includestdafx.h3.#includeiostream4.#includemath.h5.usingnamespacestd;6.7.classQueen8.{9.friendintnQueen(int);10.private:11.boolPlace(intk);12.voidBacktrack(void);13.intn,//皇后个数14.*x;//当前解15.longsum;//当前已找到的可行方案数16.};17.18.intmain()19.{20.intn=4,m;21.coutn皇后问题的解为：endl;22.m=nQueen(n);23.coutn皇后问题共有;24.coutm个不同的解!endl;25.return0;26.}27.28.boolQueen::Place(intk)29.{30.for(intj=1;jk;j++)31.{32.if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))33.{34.returnfalse;35.}36.}37.returntrue;38.}39.40.voidQueen::Backtrack()41.{42.x[1]=0;43.intk=1;44.while(k0)45.{46.x[k]+=1;47.while((x[k]=n)&&!(Place(k)))//寻找能够放置皇后的位置48.{49.x[k]+=1;50.}51.52.if(x[k]=n)//找到位置53.{54.if(k==n)55.{56.for(inti=1;i=n;i++)57.{58.coutx[i];59.}60.coutendl;61.sum++;62.}63.else64.{65.k++;66.x[k]=0;67.}68.}69.else70.{71.k--;72.}73.}74.}75.76.intnQueen(intn)77.{78.QueenX;79.X.n=n;80.X.sum=0;81.82.int*p=newint[n+1];83.84.for(inti=0;i=n;i++)85.{86.p[i]=0;87.}88.89.X.x=p;90.X.Backtrack();91.92.delete[]p;93.returnX.sum;94.}程序运行结果如图：2、0-1背包问题问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c0,wi0,vi0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。问题解析：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。算法的具体实现如下：[cpp]viewplaincopy1.//0-1背包问题回溯法求解2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.templateclassTypew,classTypep7.classKnap8.{9.templateclassTypew,classTypep10.friendTypepKnapsack(Typep[],Typew[],Typew,int);11.private:12.TypepBound(inti);13.voidBacktrack(inti);14.15.Typewc;//背包容量16.intn;//物品数17.18.Typew*w;//物品重量数组19.Typep*p;//物品价值数组20.Typewcw;//当前重量21.22.Typepcp;//当前价值23.Typepbestp;//当前最后价值24.};25.26.templateclassTypew,classTypep27.TypepKnapsack(Typepp[],Typeww[],Typewc,intn);28.29.templateclassType30.inlinevoidSwap(Type&a,Type&b);31.32.templateclassType33.voidBubbleSort(Typea[],intn);34.35.intmain()36.{37.intn=4;//物品数38.intc=7;//背包容量39.intp[]={0,9,10,7,4};//物品价值下标从1开始40.intw[]={0,3,5,2,1};//物品重量下标从1开始41.42.cout背包容量为：cendl;43.cout物品重量和价值分别为：endl;44.45.for(inti=1;i=n;i++)46.{47.cout(w[i],p[i]);48.}49.coutendl;50.51.cout背包能装下的最大价值为：Knapsack(p,w,c,n)endl;52.return0;53.}54.55.templateclassTypew,classTypep56.voidKnapTypew,Typep::Backtrack(inti)57.{58.if(in)//到达叶子节点59.{60.bestp=cp;61.return;62.}63.64.if(cw+w[i]=c)//进入左子树65.{66.cw+=w[i];67.cp+=p[i];68.Backtrack(i+1);69.cw-=w[i];70.cp-=p[i];71.}72.73.if(Bound(i+1)bestp)//进入右子树74.{75.Backtrack(i+1);76.}77.}78.79.templateclassTypew,classTypep80.TypepKnapTypew,Typep::Bound(inti)//计算上界81.{82.Typewcleft=c-cw;//剩余容量83.Typepb=cp;84.85.//以物品单位重量价值递减序装入物品86.while(i=n&&w[i]=cleft)87.{88.cleft-=w[i];89.b+=p[i];90.i++;91.}92.93.//装满背包94.if(i=n)95.{96.b+=p[i]/w[i]*cleft;97.}98.99.returnb;100.}101.102.classObject103.{104.templateclassTypew,classTypep105.friendTypepKnapsack(Typep[],Typew[],Typew,int);106.public:107.intoperator=(Objecta)const108.{109.return(d=a.d);110.}111.private:112.intID;113.floatd;114.};115.116.templateclassTy