用回溯算法解n皇后问题实验步骤

湖州师范学院实验报告课程名称：算法实验四：回溯算法一、实验目的1、理解回溯算法的概念，掌握回溯算法的基本要素。2、掌握设计回溯算法的一般步骤，针对具体问题，能应用回溯算法求解。二、实验内容1、问题描述1）n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。2）0-1背包问题需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。每种物品要么放进背包，要么丢弃。2、数据输入：文件输入或键盘输入。3、要求：1）完成上述两个问题，时间为2次课。2）独立完成实验及实验报告。三、实验步骤1、理解方法思想和问题要求。2、采用编程语言实现题目要求。3、上机输入和调试自己所写的程序。4、附程序主要代码：1.n后问题：#includeiostreamusingnamespacestd;classQueen{friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn,*x;longsum;};boolQueen::Place(intk){for(intj=1;jk;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(tn){for(inti=1;i=n;i++)coutx[i];coutendl;sum++;}else{for(inti=1;i=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}}intnQueen(intn){QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i=n;i++)p[i]=0;X.x=p;X.Backtrack(1);delete[]p;returnX.sum;}voidmain(){intn,set;cout请输入皇后个数：;cinn;cout可行方案所有解：endl;set=nQueen(n);cout可行方案数：setendl;}2.0-1背包：#includestdio.h#includeconio.hintn;//物品数量doublec;//背包容量doublev[100];//各个物品的价值doublew[100];//各个物品的重量doublecw=0.0;//当前背包重量doublecp=0.0;//当前背包中物品价值doublebestp=0.0;//当前最优价值doubleperp[100];//单位物品价值排序后intorder[100];//物品编号intput[100];//设置是否装入//按单位价值排序voidknapsack(){inti,j;inttemporder=0;doubletemp=0.0;for(i=1;i=n;i++)perp[i]=v[i]/w[i];for(i=1;i=n-1;i++){for(j=i+1;j=n;j++)if(perp[i]perp[j])perp[],order[],sortv[],sortw[]{temp=perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp=v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数voidbacktrack(inti){doublebound(inti);if(in){bestp=cp;return;}if(cw+w[i]=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)bestp)//符合条件搜索右子数backtrack(i+1);}//计算上界函数doublebound(inti){doubleleftw=c-cw;doubleb=cp;while(i=n&&w[i]=leftw){leftw-=w[i];b+=v[i];i++;}if(i=n)b+=v[i]/w[i]*leftw;returnb;}intmain(){inti;printf(请输入物品的数量和容量：);scanf(%d%lf,&n,&c);printf(请输入物品的重量和价值：);for(i=1;i=n;i++){printf(第%d个物品的重量：,i);scanf(%lf,&w[i]);printf(价值是：);scanf(%lf,&v[i]);order[i]=i;}knapsack();backtrack(1);printf(最有价值为：%lf\n,bestp);printf(需要装入的物品编号是：);for(i=1;i=n;i++){if(put[i]==1)printf(%d,order[i]);}return0;}5、实验结果：四、实验分析1、：n后问题分析只要不要在同一直线和斜线上就行。boolQueen::Place(intk){for(intj=1;jk;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}2、01背包问题分析：分为两部分一个是放入，一个是选择不放入，不放入有两种，一种是可以放入但不放，这个需要先减去前面放入后的价值，另一个是空间不允许，可以直接进入下一个。