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

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

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

3、*x;long sum;bool Queen:Place(int k) for (int j = 1; j < k; j+)if (abs(k - j) = abs(xj - xk) | (xj = xk) return false;return true;void Queen:Backtrack(int t) if (t > n) for (int i = 1; i <= n; i+)cout << xi << ""cout << endl;sum+;)else for (int i = 1; i <= n; i

4、+) 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(l);delete p;return X.sum;void main() int n, set;cout <<呼青输入皇后个数："cin >> n;cout <<，可行方案所有解："<< end

5、l;set = nQueen(n);cout << '可行方案数："<< set << endl;2.0-1背包：#include <stdio.h>#include <conio.h>int n;物品数量double c; 背包容量double v100;/ 各个物品的价值double w100;/ 各个物品的重量double cw = 0.0;/ 当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;/单位物品价值排序后i

6、nt 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(perpi<perpj) perp,order口,sortv口,sortw口 (temp = perpi; perpi=perpi; perpj=temp;temporder=orderi; orderi=orderj; order

7、j=temporder;temp = vi;vi=vj;vj=temp;temp=wi;wi=wj;wj=temp;/回溯函数void backtrack(int i)(double bound(int i);if(i>n)(bestp = cp;return;if(cw+wi<=c)(cw+=wi;cp+=vi;puti=1;backtrack(i+1);cw-=wi;cp-=vi;)if(bound(i+1)>bestp)/ 符合条件搜索右子数 backtrack(i+1);)/计算上界函数double bound(int i)double leftw= c-cw;dou

8、ble b = 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("第物品的重量：",i);scanf("%lf",&am

9、p;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