t+=M[x[i]][i];
if(t>bestf)
{
bestf=t;
for(int j=1;j<=n;j++)
bestx[j]=x[j];
}
}
else
{
for(int j=i; j<=n; j++) //自i后，有[i:n]项作业
{
Swap(x[i],x[j]); //x[j]成为第i个作业
Backtrack(i+1);
ss>>M[i][j]; //从流中读取一个T类型的数赋给M
}
}
class Flowshop
{
friend int Flow(int **,int,int []);
private:
void Backtrack(int i);
int **M; //各作业所需的处理时间
int *x; //当前位置安排
int *bestx; //当前最优攻击力
void Swap(Type &a,Type &b)
{
Type t=b;
b=a;
a=t;
}
template<typename Type> //创建二维数组
void TwoDimArray(Type** &p,int r,int c)
{
p=new Type *[r];
for(int i=0; i<r; i++)
int *f2; //机器2完成处理时间
int f1; //机器1完成处理时间
int f; //当前攻击力
int bestf; //当前最优值
int n; //角色
};
void Flowshop::Backtrack(int i)
{
if(i>n)
{
int t=0;
for(int i=1; i<=n; i++)
Main.cpp
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstdlib>
#define INT_MAX 90
using namespace std;
template<typename Type> //交换两个变量的值
实验内容：
1.排兵布阵问题
某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。
数据：
防卫点
角色
1
2
3
4
5
1
60
40
80
50
60
2
90
60
80
70
20
3
30
50
40
50
80
4
90
40
30
70
90
5
60
80
90
60
50
2. 0-1背包问题（选做）
编程实现0-1背包问题的回溯算法。
数据文件见附件。
实验要求：
1.实验报告只写实验⑴。
2.写出算法思想、主要程序代码、算法复杂性分析。
实验（1）的步骤、算法及运行结果：
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
最新文件----------------仅供参考--------------------已改成-----------word文本---------------------方便更改
赠人玫瑰，手留余香。
湖南科技学院实验报告
系部
数学与计算科学
专业
信息与计算科学
成绩评定
班级
信计0902班
学号
200905002231
int bestf;
TwoDimArray(M,5,5);
X.x=new int[n+1];
X.M=M;
X.n=n;
X.bestx=new int[n+1];
X.bestf=0;
int s=Flow(M,n,bestf);
cout<<s<<endl;
Print1(bestx,5);
return 0;
p[i]=new Type[c];
for(int i=0; i<r; i++)
for(int j=0; j<c; j++)
p[i][j]=0;
}
template<typename Type> //输出一维数组的元素
void Prin; i<=n; i++)
赠人玫瑰，手留余香。
{
cerr<<"文件打开失败！"<<endl;
exit(1); //结束程序
}
string s;
for(int i=0; i<r; ++i) //读取矩阵数据
{
getline(infile,s); //读一行
istringstream ss(s); //创建字符串流ss
for(int j=0; j<c; ++j)
X.f=0;
for(int i=0; i<=n; i++)
{
X.f2[i]=0;
X.x[i]=i;
}
X.Backtrack(1);
delete[] X.x;
delete[] X.f2;
return X.bestf;
}
int main()
{
Flowshop X;
int **M;
int n;
int *bestx;
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
2.回溯法的实现。
打开Codeblocks10.05，编辑头文件Queue.h和主程序main.cpp,利用参考程序，同时还设计了从文件读入数据，使程序更清晰，其主要程序如下：
}
运行结果：
实验总结
今天主要学的是回溯法，由于上一次实验老师要求我们从文件输入数据，因此这一次我同样利用了该种方式，将矩阵中的数据仍从文件输入，还挺好上手的，但是本该顺畅的实验过程中却出现了一个笨错误，就是我的程序调试总是不正确，我还想着明明就和别人的差不多，不应该啊~但是别的同学都可以运行了，我很纠结，又反复看了很多遍，后面才知道是头文件的引用不正确，我汗！改好头文件，程序一下子就顺利运行了，有种山重水复疑无路的感觉，虽然那个错误很白痴~额~
cout<<a[i]<<' ';
cout<<endl;
}
template<typename T>
void InputData2(T **M,int r,int c,char *filename)
{
ifstream infile;
infile.open(filename); //打开文件
if(!infile) //测试是否已经成功地打开了文件
Swap(x[i],x[j]);
}
}
}
int Flow(int **M,int n,int bestx[])
{
Flowshop X;//初始X对象的数据
X.x=new int[n+1];
X.f2=new int[n+1];
X.M=M;
X.n=n;
X.bestx=bestx;
X.bestf=0;
X.f1=0;
最后是算法时间复杂度分析，因为算法Backtrack在每个结点处耗费O(1)计算时间，故最坏情况下，整个算法的时间复杂性为O(n!)
最新文件----------------仅供参考--------------------已改成-----------word文本---------------------方便更改
姓名
易丹
课程名称
算法设计与分析
实验时间
2012.5.18
实验编号
实验四
实验名称
回溯法
实验环境
D315、一台电脑、Codeblocks10.05
实验目的
1.理解回溯法的深度优先搜索策略。
2.掌握用回溯法解题的算法框架。
3.掌握回溯法的设计策略。
实验内容（①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）
