算法设计与分析实验4报告

    编程实现0-1背包问题的回溯算法。

    数据文件见附件。

实验要求：

    1. 实验报告只写实验⑴。

2. 写出算法思想、主要程序代码、算法复杂性分析。

实验（1）的步骤、算法及运行结果：

 1. 回溯法的总体思想

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

2.回溯法的实现。

打开Codeblocks10.05，编辑头文件Queue.h和主程序main.cpp,利用参考程序，同时还设计了从文件读入数据，使程序更清晰，其主要程序如下：

Main.cpp

#include

#include

#include

#include

#define  INT_MAX  90

using 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        p[i]=new Type[c];

for(int i=0; ifor(int j=0; j            p[i][j]=0;

}

template //输出一维数组的元素

void Print1(Type a[],int n)

{

for(int i=1; i<=n; i++)

cout<cout<}

template

void InputData2(T **M,int r,int c,char *filename)

{

    ifstream infile;

    infile.open(filename);  //打开文件

    if(!infile)   //测试是否已经成功地打开了文件

    {

        cerr<<"文件打开失败！"<        exit(1);  //结束程序

    }

    string s;

    for(int i=0; i    {

        getline(infile,s); //读一行

        istringstream ss(s); //创建字符串流ss

for(int j=0; jss>>M[i][j]; //从流中读取一个T类型的数赋给M

    }

}

class Flowshop

{

    friend int Flow(int **,int,int []);

private:

    void Backtrack(int i);

    int **M;  //各作业所需的处理时间

    int *x; //当前位置安排

    int *bestx;  //当前最优攻击力

    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++)

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

                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;

    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;

    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<    Print1(bestx,5);

    return 0;

}

运行结果：