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

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

2、的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。每种物品要么放进背包，要么丢弃。2、数据输入：文件输入或键盘输入。3、要求：1）完成上述两个问题，时间为 2 次课。2）独立完成实验及实验报告。三、 实验步骤1、 理解方法思想和问题要求。2、 采用编程语言实现题目要求。3、 上机输入和调试自己所写的程序。4、附程序主要代码：1.n后问题：#includeusing namespace std;class Queen friend int nQueen(int);private:bool Place(int k);void Backtrack(int t);int n, *x; lo

3、ng sum; ;bool Queen:Place(int k) for (int j = 1; j n) for (int i = 1; i = n; i+)cout xi ; cout endl; sum+;else for (int i = 1; i = n; i+) xt = i;if (Place(t) Backtrack(t + 1);int nQueen(int n) Queen X;/初始化XX.n = n;X.sum = 0;int* p = new intn + 1;for (int i = 0; i = n; i+)pi = 0;X.x = p;X.Backtrack(1

4、);delete p;return X.sum;void main() int n, set;cout n;cout 可行方案所有解： endl;set = nQueen(n);cout 可行方案数： set endl;2.0-1背包：#include #include int n;/物品数量double c;/背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;/单位物品价值排序

5、后int order100;/物品编号int put100;/设置是否装入/按单位价值排序void knapsack() int i,j; int temporder = 0; double temp = 0.0; for(i=1;i=n;i+) perpi=vi/wi; for(i=1;i=n-1;i+) for(j=i+1;j=n;j+) if(perpin) bestp = cp; return; if(cw+wibestp)/符合条件搜索右子数 backtrack(i+1);/计算上界函数double bound(int i) double leftw= c-cw; double b

6、= cp; while(i=n&wi=leftw) leftw-=wi; b+=vi; i+; if(i=n) b+=vi/wi*leftw; return b;int main() int i; printf(请输入物品的数量和容量：); scanf(%d %lf,&n,&c); printf(请输入物品的重量和价值：); for(i=1;i=n;i+) printf(第%d个物品的重量：,i); scanf(%lf,&wi); printf(价值是：); scanf(%lf,&vi); orderi=i; knapsack(); backtrack(1); printf(最有价值为：%lfn,bestp); printf(需要装入的物品编号是：); for(i=1;i=n;i+) if(puti=1) printf(%d ,orderi); return 0;5、实验结果：四、 实验分析1、：n后问题分析只要不要在同一直线和斜线上就行。bool Queen:Place(int k) for (int j = 1; j k; j+)if (abs(k - j) = abs(xj - xk) | (xj = xk)retu