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

《用回溯算法解n皇后问题实验步骤》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、湖州师范学院实验报告课程名称：算法实验四：回溯算法一、实验目的1、理解冋溯算法的概念，掌握回溯算法的基本要素。2、掌握设计回溯算法的一般步骤，针对具体问题，能应用回溯算法求解。二、实验内容1、问题描述1)n后问题在ns格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。2)0-1背包问题需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载

2、，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。每种物品要么放进背包，要么丢弃。2、数据输入：文件输入或键盘输入。3、要求：1)完成上述两个问题，时间为2次课。2)独立完成实验及实验报告。三、实验步骤1、理解方法思想和问题要求。2、采用编程语言实现题目要求。3、上机输入和调试自己所写的程序。4、附程序主要代码：l・n后问题：#includeusingnamespacestd;classQueen{friendintnQueen(int);private:boolPlace(intk);voidBackt

3、rack(intt);intn,*x;longsum;}；boolQueen::Place(intk){for(intj=1;jn){for(inti=1;i<=n;i++)cout«x[i]«Hcout«endl;sum++;}else{for(inti=1;i<=n;i++){x[t]=i；if(Place(t))Backtrack(t

4、+1);}}}intnQueen(intn){QueenX;〃初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti二0;iv二n;i++)P[i]=0;X.x=p;X.Backtrack(l);delete[]p;returnX.sum;}voidmain(){intn,set;cout«”请输入皇后个数cin»n;cout«"可行方案所有解："《endl;set=nQueen(n);cout«”可行方案数:"«set«endl;}2.0-1背包：#inelude〈stdio.h>Sinclude

5、>intn；〃物品数量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=l；i<=n；i

6、++)perp[i]=v[i]/w[i]；for(i=l；i<=nT；i++){for(j=i+l；j<=n；j++)if(perp[i]

7、backtrack(inti){doublebound(inti)；if(i>n){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+二讥i]

8、；i++;}辻(i<=n)b+=v[i]/w[i]*leftw；returnb；}intmain(){inti；print