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

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

2、 ，价值为 pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。每种物品要么放进背包，要么丢弃。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(i

3、nt k);void Backtrack(int t);int n, *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;

4、 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);delete p;return X.sum;void main() int n, set;cout << "请输入皇后个数：" cin >&g

5、t; n;cout << "可行方案所有解：" << endl;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;/当前背包中物品价值

6、double bestp = 0.0;/当前最优价值double perp100;/单位物品价值排序后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(perpi<perpj) perp,order,sortv,sortw temp = perpi; perpi=per

7、pi; perpj=temp; temporder=orderi; orderi=orderj; orderj=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)/符合条件搜索

8、右子数 backtrack(i+1);/计算上界函数double bound(int i) double leftw= c-cw; double 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("请输入物品的重量和价值："

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