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

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

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

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

3、riendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn,*x;longsum;};boolQueen::Place(intk){for(intj=1;j

4、

5、(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n){for(inti=1;i<=n;i++)cout

6、<

7、请输入皇后个数：";cin>>n;cout<<"可行方案所有解："<#includeintn;//物品数量doublec;//背包容量doublev[100];//各个物品的价值doublew[100];//各个物品的重量doublecw=0.0;//当前背包重量doublecp=0.0;//当前背包中物品价值doublebestp=0.

8、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]

9、[],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(i>n){bestp=cp;return;}if(cw+w[i]

10、<=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