湖南科技学院实验报告系部数学与计算科学专业信息与计算科学成绩评定班级信计 0902 班学号姓名易丹课程名称算法设计与分析实验时间.5.18实验编号实验四实验名称回溯法实验环境D315、一台电脑、Codeblocks10.05实验目的1. 理解回溯法的深度优先搜索方略。2. 掌握用回溯法解题的算法框架。3. 掌握回溯法的设计方略。实验内容（①算法、程序、环节和办法 ②输入、输出、实验成果 ③实验成果分析）实验内容： 1. 排兵布阵问题某游戏中，不同的兵种处在不同的地形上其攻击能力不同，现有 n 个不同兵种的角色{1,2,...,n}，需安排在某战区 n 个点上，角色 i 在 j 点上的攻击力为 Aij。试设计一种布阵方案，使总的攻击力最大。数据：防卫点角色1234516040805060290608070203305040508049040307090560809060502. 0-1 背包问题（选做）编程实现 0-1 背包问题的回溯算法。数据文献见附件。实验规定： 1. 实验报告只写实验⑴。2. 写出算法思想、重要程序代码、算法复杂性分析。实验（1）的环节、算法及运行成果： 1. 回溯法的总体思想回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种办法合用于解某些组合数相称大的问题。回溯法在问题的解空间树中，按深度优先方略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点与否包含问题的解。如果必定不包含，则跳过对该结点为根的子树的搜索，逐级向其祖先结点回溯；否则，进入该子树，继续按深度优先方略搜索。2.回溯法的实现。打开 Codeblocks10.05，编辑头文献 Queue.h 和主程序 main.cpp,运用参考程序，同时还设计了从文献读入数据，使程序更清晰，其重要程序以下：Main.cpp#include
#include #include #include #define INT_MAX 90using namespace std;template //交换两个变量的值void Swap(Type &a,Type &b){ Type t=b; b=a; a=t;}template //创立二维数组void TwoDimArray(Type** &p,int r,int c){ p=new Type *[r]; for(int i=0; i //输出一维数组的元素void Print1(Type a[],int n){ for(int i=1; i<=n; i++) cout<
