算法设计实验报告

实 验 报 告

|

|

             实验名称       算法设计与分析综合实验                 

课程名称         算法设计与分析              

|

|

                 专业班级：      学生姓名： 

                 学    号：      成    绩：

指导教师：         实验日期： 

[—归并排序

一、实验目的及要求

归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。

实验要求：

（1）编写一个模板函数：template ，MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator<(const T&x,const T&y);比较运算符的类型进行排序。

（2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。

二、所用仪器、设备

计算机、Visual C++软件。

三、实验原理

分治原理：

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互且与原问题性质相同。求出子问题的解，就可得到原问题的解。当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

归并原理：

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

四、实验方法与步骤

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

实现时间计量：

#define _CLOCK_T_DEFINED

srand((unsigned)time(0));

//定义一数组a[n];对每一个赋予一值。

a[i]=rand();得到随即数。        

duration =(double)(finish -start)/CLOCKS_PER_SEC;

start=clock();将系统时间赋予Start。以便以后进行比较。

std::sort(b,b+1000);系统执行1000个数据。

Finish-Start为最终结果。

五、实验结果与数据处理

实验结果截图：

实验代码：

#include

#include

#include

#include

#include

using namespace std;

template

void MergSort(Type a[], int n){

    Type *b = new Type[n];

    int s = 1;

while (s < n){

        MergPass(a, b, s, n);

        s += s;

        MergPass(b, a, s, n);

        s += s;

    }

}

template

void MergPass(Type x[], Type y[], int s, int n)

{

    int i = 0;

while (i <= n - 2 * s)

    {

        Merg(x, y, i, i + s - 1, i + 2 * s - 1);

        i = i + 2 * s;

    }

if (i + s < n)

        Merg(x, y, i, i + s - 1, n - 1);

    else{                                       

        for (int j = i; j <= n - 1; j++){

            y[j] = x[j];

        }

    }

}

template

void Merg(Type c[], Type d[], int l, int m, int r){

    int i = l, j = m + 1, k = l;

while ((i <= m) && (j <= r)){

        if (c[i] <= c[j])

            d[k++] = c[i++];

        else

            d[k++] = c[j++];

    }

if (i>m)

for (int q = j; q <= r; q++)

        d[k++] = c[q];

    else

for (int q = i; q <= m; q++)

        d[k++] = c[q];

}

float randf(float base, float up){    

return (rand() % (int)((up - base) * RAND_MAX))/(float)RAND_MAX ; //产生随机数

}

void printArray(float *a,int N){

for(int i=0;i<=N;i++){

        if((i%8==0)&&(i>0))

        {

         cout<        }

        else{

        cout<        }

    }

}

void main(){

    int ArrayLen = 5;

    cout<<"请输入元素个数："< cin>>ArrayLen;

    float *array = new float[ArrayLen];

    float *arrays = new float[ArrayLen];

    float  mn, ene;

    printf("数组已建立：    \\n");

    srand((unsigned)time(NULL)); //设置随机数的seed

for (int i = 0; i < ArrayLen; i++)

    {

        mn = (float)rand(); //产生小数

        ene = randf(1,10000)+mn;

        arrays[i] =ene;

        array[i] = ene;

    }    

    //cout<<"需要排序的归并数组:\\n";

    //printArray(array, ArrayLen);

    int flag = 1;

    while (flag != 0){

        cout<<"\\n输入需要显示的排序方法："<        cout << "1.归并排序   2.std排序    0.退出" << endl;

        cin >> flag;

        switch (flag){

        case 0:

            break;

        case 1:

            {

            clock_t s = 0, e = 0;

            s = clock();

            MergSort(array, ArrayLen);

            e = clock();    

            //cout<<"排序后的序列为："<            //printArray(array, ArrayLen);

            cout << "\\nMergSort运行了：" << (e - s) << "ms" << endl;

            break;

            }

        case 2:{

            clock_t start1 = 0, end1 = 0;

            start1 = clock();

            std::sort(&arrays[0], &arrays[ArrayLen]);

            end1 = clock();

            //printArray(array, ArrayLen);

            cout << "\\nstd::sort运行了：" << (end1 - start1) << "ms" << endl;

            break;

               }

        }

    }

}

[综合实验 二] 贪心算法—Huffman树及Huffman编码

一、实验目的及要求

一个记录字符及出现频率的文件如下所示：

huffman.haf

7

a,45

b,13

c,12

d,16

e,

f,34

g,20

试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：

        CHuffman hm("huffman.dat");

        hm.CreateTree();

        hm.OutputTree();

        hm.OutputCode(); //二进制形式的字符串

对于输出树的形式可自行决定(如图形界面或字符界面)。

二、所用仪器、设备

计算机、Visual C++软件。

三、实验原理

贪心原理：

(1) 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

(2) 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

(3) 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

(4) 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

(5) 最后，目标函数给出解的值。

(6) 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

Huffman原理：

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

四、实验方法与步骤

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为。也是字符c的前缀码长。

该编码方案的平均码长定义为：B（T）使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率为合并的两棵树的频率之和，并将新树插入优先队列中。

优先队列，优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.

五、实验结果与数据处理

主要代码如下：

Huffman::Huffman(char *sFileName1)

{

this->sFileName = sFileName1;

    ifstream fin(sFileName);

    char  ch[4];

    fin.getline(ch, 4);

    int n1 = atoi(ch);

    cout << "节点数目:   "< this->n = n1;

this->t = new THaffmanNode[2 * n1 - 1];

this->nNext = n1;

    char ch1;

for (int i = 0; i    {

        fin.get(ch1);

        t[i].c = ch1;

        fin.ignore(100, ',');

        fin.getline(ch, 4);

        t[i].f = atoi(ch);

    }

for (int i = 0; i    {

        cout << t[i].c << " " << t[i].f << endl;

    }

for (int i = 0; i    {

        t[i].idx = i;

        PQ.push(t[i]);

    }

    while (!PQ.empty())

    {

        if ((PQ.size()) >= 2)

        {

            THaffmanNode nn, nr, nl;

            nl = PQ.top();

            PQ.pop();

            nr = PQ.top();

            PQ.pop();

            nn.f = nl.f + nr.f;

            nn.l = nl.idx;

            nn.r = nr.idx;

            nn.idx = nNext++;

            t[nl.idx].p = nn.idx;

            t[nr.idx].p = nn.idx;

            t[nn.idx] = nn;

            PQ.push(nn);

        }

        else

        {

            t[2 * n - 2].p = -1;

            break;

        }

    }

}

Huffman::~Huffman(void)

{

}

void Huffman::OutputTree()

{

for (int i = 0; i<2 * n - 1; i++)

    {

        cout << "权重：" << t[i].f << "   ";

        cout << "左孩子：" << t[i].l << "   ";

        cout << "右孩子：" << t[i].r << "   ";

        cout << "父节点：" << t[i].p << "   ";

        cout << "在数组的位置：" << t[i].idx << endl;

    }

    //现在数组中存的是哈弗曼数

}

void Huffman::OutputCode()

{

    //用stack 来依次记录各编码的0 1 编码

std::stack> sk;

    THaffmanNode ntemp, ntemp1;

for (int i = 0; i    {

        ntemp = t[i];

        while (ntemp.p != -1)

        {

            ntemp1 = t[ntemp.p];

            if (t[ntemp1.l].idx == ntemp.idx)

            {

                sk.push(0);

                ntemp = ntemp1;

            }

            else

            {

                sk.push(1);

                ntemp = ntemp1;

            }

        }

        int i1 = sk.size();

        cout << t[i].f << " ：  ";

        for (int i = 0; i        {

            cout << sk.top();

            sk.pop();

        }

        cout << endl;

    }

}

实验结果截图：

一、实验目的及要求

问题：对任意给定的n求解n后问题。

具体要求：

1．封装n后问题为类，编写以下两种算法进行求解：

（1）递归回溯方法；

（2）迭代回溯方法。(选)

2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；

3．构造n后问题的解数表格（由程序自动生成）:

计算机、Visual C++软件。

三、实验原理

回溯原理：

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

1、定义一个解空间，它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

四、实验方法与步骤

n后问题等于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。

K：第K个皇后，也表示第K行

X[i]：第K个皇后在第K行的 第i列

皇后k在第k行第x[k]列时，x[i]==x[k]时，两皇后在同一列上;abs(x[i]-x[k])==abs(i-k)时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返回false表示不符合条件。

五、实验结果与数据处理

实验结果截图：

实验代码：

#include

#include

class Queen

{

friend int nQueen(int);

private:

    bool Place(int k);

    void Backtrack(int t);

    int n,*x;      //当前解

    long sum;   //当前已找到的可行方案数

};

bool Queen::Place(int k)

{

for (int j=1;j    if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;

  return true;

} 

void Queen::Backtrack(int t)

{    

if (t>n)

  {

      sum++;//达到叶结点

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

      {

          cout<      }

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

       {

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

           {

           if(x[i]!=j)

                cout<<"." ;

           else

cout<<"#";

           }

           cout<    }

cout<  }

    else

      for (int i=1;i<=n;i++) {       //搜索子结点

        x[t]=i;                       //进入第i个子结点

        if (Place(t)) Backtrack(t+1);

      }

 }

int nQueen(int n)

{

Queen X;

//初始化X

X.n=n;

X.sum=0;

int *p=new int [n+1];

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

  p[i]=0;

X.x=p;

X.Backtrack(1);        //对整个解空间回溯搜索

delete []p;

return X.sum;

}

void main()

{

    int a=0,b=0;

    cout<<"********欢迎进入皇后问题*********"<    int flag=1;

    while(flag){

    cout<<"请输入皇后数"< cin>>a;

    b=nQueen(a);

    cout<<"方案个数："<    cout<<"是否继续？1为是，0为否"< cin>>flag;

    }

}

[综合实验四]    背包问题的贪心算法

一、实验目的及要求

问题: 

给定如下n种物品的编号，及其价值；背包重量为c, 求最佳装包方案，才能使其装入背包的价值最大。

将背包问题进行类的封装；

能对任意给定的n种物品的重量、价值及背包限重，输出以上表格( 或纵向输出)；

输出背包问题的解；

本题要求采用STL库中的排序算法数据进行排序。

二、所用仪器、设备

计算机、Visual C++软件。

三、实验原理

贪心算法解决背包问题有几种策略：

（1）一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

（2）另一种方案是重量贪心准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。

（3）还有一种贪心准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。

四、实验方法与步骤

首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超出C，则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装满为止。

采用贪婪准则：每次选择p/w最大的物品放入背包。

注意在这之前的计算每种物品单位重量的价值Vi/Wi后，进行排序。

五、实验结果与数据处理

实验截图：

主要代码如下：

#include

#define M 4  

struct node{ 

  float no;//编号

  float value; 

  float weight; 

  float wweight;//若是最后一个的用量

  int flag; 

}Node[M],temp; 

float Value,curvalue=0; 

float Weight,curweight=0;  

//按性价比排序  

void sort()

{ 

     int i,j; 

for(i=0;i     { 

for(j=i+1;j         {       if((Node[i].value/(float)Node[i].weight)             { 

                temp=Node[i]; 

                Node[i]=Node[j]; 

                Node[j]=temp; 

             } 

         } 

     } 

} 

//可切割装载方法

void load2(){

    int i; 

for(i=0;i if((Node[i].weight+curweight)<=Weight)

        { 

         curvalue+=Node[i].value; 

         curweight+=Node[i].weight; 

         Node[i].flag=1; 

        }

        else if((Node[i].weight+curweight)>Weight&&(curweight            float t=Weight-curweight;

            curvalue+=(Node[i].value)/(Node[i].weight)*t;

            curweight=Weight;

            Node[i].flag=2;

            Node[i].wweight=t;

        }

        else{ 

         Node[i].flag=0; 

        }    

    } 

} 

//进行结果的输出  

void putout(){ 

    int i; 

    printf("选中物品的编号和重量分别为：");

    printf("\\n\\r");

for(i=0;i        if(Node[i].flag==1){ 

          printf("%.2f",Node[i].no);

          printf("  ");

          printf("%.2f",Node[i].weight);

          printf("\\n\\r");

        } 

        else if(Node[i].flag==2){

             printf("%.2f",Node[i].no);

          printf("  ");

          printf("%.2f",Node[i].wweight);

          printf("\\n\\r");

        } 

    } 

    printf("\\n总价值为:%.2f",curvalue); 

}  

int main(){ 

    int i; 

    static int p;

    printf("请输入物品的重量和价值：\\n"); 

for(i=0;i       printf("请输入第%d个物品的重量和价值",i+1); 

       scanf("%f%f%f",&Node[i].no,&Node[i].weight,&Node[i].value);

    } 

    printf("\\n请输入背包容积："); 

    scanf("%f",&Weight); 

    sort();

    load2();

    putout();

  return 0; 

}

[综合实验 六] (选做)  0-1背包问题的求解

一、实验内容：

0-1背包问题有多种解法，如动态规划方法，回溯方法，分枝限界方法等。对于同一种问题，请参照教材中的算法，给出相应的程序实现。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：

1.动态规划法求解0/1背包问题：

1）基本思想：

令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：

按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。

2）代码：

    #include

    #include

    using namespace std;

    #define N 100    //最多可能物体数

    struct goods    //物品结构体

    {

        int sign;    //物品序号

        int w;    //物品重量

        int p;    //物品价值

    }a[N];

    bool m(goods a,goods b)

    {

      return (a.p/a.w)>(b.p/b.w);

    }

    int max(int a,int b)

    {

        return a    }

    int n,C,bestP=0,cp=0,cw=0;

    int X[N],cx[N];

    int KnapSack2(int n,goods a[],int C,int x[])

    {

        int V[N][10*N];

        for(int i=0;i<=n;i++)    //初始化第0列

            V[i][0]=0;

        for(int j=0;j<=C;j++)    //初始化第0行

            V[0][j]=0;

         for(i=1;i<=n;i++)        //计算第i行，进行第i次迭代

            for(j=1;j<=C;j++)

                if(j                     V[i][j]=V[i-1][j];

                else

                   V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);

                j=C;    //求装入背包的物品

                for (i=n;i>0;i--)

                {

                    if (V[i][j]>V[i-1][j]){

                        x[i-1]=1;

                        j=j-a[i-1].w;

                    }

                    else    x[i-1]=0;

                }

                return V[n][C];    //返回背包取得的最大价值

     }

    int main()

    {

        goods b[N];

        printf("物品种数n: ");

        scanf("%d",&n);    //输入物品种数

        printf("背包容量C: ");

        scanf("%d",&C);    //输入背包容量

        for (int i=0;i        {

            printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

            scanf("%d%d",&a[i].w,&a[i].p);

            b[i]=a[i];

         }

     int sum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题

         printf("动态规划法求解0/1背包问题:\\nX=[ ");

         for(i=0;i            cout<        printf("]    装入总价值%d\\n",sum2);

        for (i=0;i        {

            a[i]=b[i];

        }//恢复a[N]顺序

    }

3）运行结果：

  4）复杂度分析:

动态规划法求解0/1背包问题的时间复杂度为：。

2.回溯法求解0/1背包问题：

1）基本思想：

回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。

2）代码:

       #include

       #include

       using namespace std;

       #define N 100    //最多可能物体数

       struct goods    //物品结构体

       {

           int sign;    //物品序号

           int w;    //物品重量

           int p;    //物品价值

       }a[N];

       bool m(goods a,goods b)

       {

           return (a.p/a.w)>(b.p/b.w);

       }

       int max(int a,int b)

       {

           return a       }

       int n,C,bestP=0,cp=0,cw=0;

       int X[N],cx[N];

       int BackTrack(int i)

      {

           if(i>n-1){

               if(bestP                    for (int k=0;k                   bestP=cp;

               }

               return bestP;

           }

if(cw+a[i].w<=C){    //进入左子树

               cw=cw+a[i].w;

               cp=cp+a[i].p;

               cx[a[i].sign]=1;    //装入背包

               BackTrack(i+1);

               cw=cw-a[i].w;

               cp=cp-a[i].p;    //回溯，进入右子树

           }

           cx[a[i].sign]=0;    //不装入背包

           BackTrack(i+1);

           return bestP;

       }

       int KnapSack3(int n,goods a[],int C,int x[])

       {

           for(int i=0;i           {

               x[i]=0;

               a[i].sign=i;

           }

            sort(a,a+n,m);//将各物品按单位重量价值降序排列

           BackTrack(0);

           return bestP;

       }

       int main()

       {

           goods b[N];

           printf("物品种数n: ");

           scanf("%d",&n);    //输入物品种数

           printf("背包容量C: ");

           scanf("%d",&C);    //输入背包容量

           for (int i=0;i           {

               printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

               scanf("%d%d",&a[i].w,&a[i].p);

               b[i]=a[i];

           }

       int sum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题

           printf("回溯法求解0/1背包问题:\\nX=[ ");

           for(i=0;i            cout<            printf("]    装入总价值%d\\n",sum3);

           for (i=0;i          {

               a[i]=b[i];

          }//恢复a[N]顺序

3）运行结果：

4）复杂度分析：

最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：。由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。

空间复杂度：有个物品，即最多递归层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为。

3.分支限界法求解背包问题：

1）基本思想：

分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。

在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

2）代码:

#include

#include

using namespace std;

#define N 100    //最多可能物体数

struct goods    //物品结构体

{

    int sign;    //物品序号

    int w;    //物品重量

    int p;    //物品价值

}a[N];

bool m(goods a,goods b)

{

return (a.p/a.w)>(b.p/b.w);

}

int max(int a,int b)

{

return a}

int n,C,bestP=0,cp=0,cw=0;

int X[N],cx[N];

struct KNAPNODE    //状态结构体

{

    bool s1[N]; //当前放入物体

    int k;        //搜索深度

    int b;    //价值上界

    int w;    //物体重量

    int p;    //物体价值

};

struct HEAP    //堆元素结构体

{

    KNAPNODE *p;//结点数据

    int b;        //所指结点的上界

};

//交换两个堆元素

void swap(HEAP &a, HEAP &b)

{

    HEAP temp = a;

    a = b;

    b = temp;

}

//堆中元素上移

void mov_up(HEAP H[], int i)

{

    bool done = false;

    if(i!=1){

        while(!done && i!=1){

            if(H[i].b>H[i/2].b){

                swap(H[i], H[i/2]);

            }else{

                done = true;

            }

            i = i/2;

        }

    }

}

//堆中元素下移

void mov_down(HEAP H[], int n, int i)

{

    bool done = false;

if((2*i)<=n){

        while(!done && ((i = 2*i) <= n)){

            if(i+1<=n && H[i+1].b > H[i].b){

                i++;

            }

            if(H[i/2].b                swap(H[i/2], H[i]);

            }else{

                done = true;

            }

        }

    }

}

//往堆中插入结点

void insert(HEAP H[], HEAP x, int &n)

{

    n++;

    H[n] = x;

    mov_up(H,n);

}

//删除堆中结点

void del(HEAP H[], int &n, int i)

{

    HEAP x, y;

    x = H[i]; y = H[n];

    n --;

if(i<=n){

        H[i] = y;

        if(y.b>=x.b){

            mov_up(H,i);

        }else{

            mov_down(H, n, i);

        }

    }

}

//获得堆顶元素并删除

HEAP del_top(HEAP H[], int &n)

{

    HEAP x = H[1];

    del(H, n, 1);

    return x;

}

//计算分支节点的上界

void bound( KNAPNODE* node, int M, goods a[], int n)

{

int i = node->k;

float w = node->w;

float p = node->p;

    if(node->w>M){    //  物体重量超过背包载重量

        node->b = 0;    //  上界置为0

    }else{

        while((w+a[i].w<=M)&&(i            w += a[i].w;   // 计算背包已装入载重

            p += a[i++].p;  //    计算背包已装入价值

        }

        if(i            node->b = p + (M - w)*a[i].p/a[i].w;

        }else{

            node -> b = p;

        }

    }

}

//用分支限界法实现0/1背包问题

int KnapSack4(int n,goods a[],int C, int X[])

{

    int i, k = 0;      // 堆中元素个数的计数器初始化为0

    int v;

    KNAPNODE *xnode, *ynode, *znode;

    HEAP x, y, z, *heap;

    heap = new HEAP[n*n];         // 分配堆的存储空间

for( i=0; i        a[i].sign=i;        //记录物体的初始编号

    }

    sort(a,a+n,m);              // 对物体按照价值重量比排序

    xnode = new KNAPNODE;         // 建立父亲结点

    for( i=0; i        xnode->s1[i] = false;

    }

xnode->k = xnode->w = xnode->p = 0;

while(xnode->k        ynode = new KNAPNODE;      // 建立结点y

        *ynode = *xnode;          //结点x的数据复制到结点y

        ynode->s1[ynode->k] = true;     //   装入第k个物体

        ynode->w += a[ynode->k].w;     //   背包中物体重量累计

        ynode->p += a[ynode->k].p;     //   背包中物体价值累计

        ynode->k ++;                //  搜索深度++

        bound(ynode, C, a, n);  //       计算结点y的上界

        y.b = ynode->b;

        y.p = ynode;

        insert(heap, y, k);        //结点y按上界的值插入堆中

        znode = new KNAPNODE;      // 建立结点z

        *znode = *xnode;           //结点x的数据复制到结点z

        znode->k++;                         //   搜索深度++

        bound(znode, C, a, n);  //计算节点z的上界

        z.b = znode->b;

        z.p = znode;

        insert(heap, z, k);      //结点z按上界的值插入堆中

        delete xnode;

        x = del_top(heap, k);    //获得堆顶元素作为新的父亲结点

        xnode = x.p;

    }

v = xnode->p;

    for( i=0; i        if(xnode->s1[i]){

            X[a[i].sign] =1 ;

        }else{

            X[a[i].sign] = 0;

        }

    }

    delete xnode;

    delete heap;

    return v;              //返回背包中物体的价值

}

void main()

{

    goods b[N];

    printf("物品种数n: ");

    scanf("%d",&n);    //输入物品种数

    printf("背包容量C: ");

    scanf("%d",&C);    //输入背包容量

    for (int i=0;i    {

        printf("物品%d的重量w[%d]及其价值v[%d]:  ",i+1,i+1,i+1);

        scanf("%d%d",&a[i].w,&a[i].p);

        b[i]=a[i];

    }

int sum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题

    printf("分支限界法求解0/1背包问题:\\nX=[ ");

for(i=0;i        cout<    printf("]    装入总价值%d\\n",sum4);

}

3)运行结果：

4)复杂度分析

 分支限界法求解0/1背包问题的时间复杂度为：。

六、实验心得

此次做完了5个算法实验，c++编程能力得到了一定的提高，指针的使用，进一步熟练，而且充分体会到c++指针的灵活带来的便利是其他编程语言无可比拟的。

在分治策略归并排序时，深入了解了分治策略的使用及归并排序的基本原理，知道它是怎么实现排序的，并通过编程实现了归并排序。也第一次运用了库函数，学到了很多知识。在此次编程中，第一次使用了vector向量及array数组，它们的优势在于动态添加元素，并且具有栈的一系列操作，十分方便。

优先队列的使用，使得排序更加简便，