计算机算法设计分析实验报告

《计算机算法设计分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-华北电力大学科技学院实验报告

2、

3、实验名称算法设计与分析课程名称算法设计与分析

4、

5、专业班级：计算机10k1学生姓名：孙刚学号：101909010121成绩：指导教师：牛为华实验日期：2012-11.---一,实验内容0-1背包问题问题描述：假设有n个物品，用Xi表示第i个物品入选与否，诺等于1表示入选，要是等于0，则表示不入选。用Pi表示物品的价值，Wi表示物品的体积，背包的体积为C，求：在不超过背包体积的前提下，让背包的所装物品的价值最大。N后问题问题描述：要求在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击。一个皇后可以攻击与之处在同一行或同

6、一列或同一斜线上的任何其他棋子。二，实验步骤对于0-1背包问题，有两种假设去解决他。假设一：求每个物品的单位体积价值，再从大到小网体积C里装，但问题是可能会装不满或者装不下，所以假设一可以排除。假设二：用完全二叉树去穷举，但时间复杂度为指数级，也不可取。现在，（1）设X1=0；A2到An选诺干物品体积之和不超过C，求最大价值之和。（2）设X2=1；A2到An选诺干物品体积之和不超过C-W1求最大价值之和。.---M【i】【j】=M【i+1】【j】Xi=0；M【i】【j】=M【i+1】【j-Wi】+PiXi=1取这两个中较大的一个，出口：M【n】【j】=

7、PnWn≤jM【n】【j】=0Wn＞j算法描述如下：voidKnapsack(intv[],intw[],intc,intn,intm[6][N]){   inti,j,jMax,k;   jMax=(w[n]-1   for(i=0;i<=jMax;i++)   {      m[n][i]=0;   }for(i=w[n];i<=c;i++)   {      m[n][i]=v[n];   } for(i=n-1;i>1;i--)   {      jMax=(w[i]-1      for(j=0

8、;j<=jMax;j++)      {         m[i][j]=m[i+1][j];      }      for(j=w[i];j<=c;j++)      {         k=j-w[i];         if(m[i+1][j]            m[i][j]=m[i+1][k]+v[i];         else            m[i][j]=m[i+1][j];      }   }  m[1][c]=m[2][c];   if(c>=w[1])   {  

9、    k=c-w[1];     .--- m[1][c]=(m[2][c]>m[2][k]+v[1])?m[2][c]:m[2][k]+v[1];   }}对与n皇后问题问题的解可表示为x[1:n]，表示皇后i放在棋盘的第i行的第x[i]列。a)x[i]≠x[j],i≠j：不允许将任何两个皇后放在同一列上；b)

10、j-i

11、≠

12、x[j]-x[i]

13、:不允许两个皇后位于同一条斜线上。问题的解空间的形式为：要找出”四皇后”问题的解，最可靠的方法就是把各种情况全部检核一遍，将符合条件A的解找出来。但这样做，你要有相当耐心才行，这是很费时的。采用回溯算法进行求

14、解，在搜索的过程中，将不满足条件要求的分支树减去，可以有效的降低算法的时间复杂性。算法描述如下：classQueen{friendintnQueen(int);private:boolPlace(k);voidBacktrack(intt);intn;//皇后个数int*x;//当前解longsum;//当前已找到的可行方案数.---};boolQueen::Place(intk){for(intj=1;j

15、

16、(x[j]==x[k]))returnfalse;returntrue;}

17、voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}intnQueen(intn){Queenx;x.n=n;x.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;x.x=p;x.Backtrack(1);delete[]p;returnx.sum;}三，实验结果0-1背包.---N皇后问题：.---.---四实验心得这次实验所做的都是老师上课讲过的实例

18、，所以实现起来还是相对比较简单的，但是在做的过程中，我对动态规划法还不是特别的理解，要是让我自