河北工业大学2016算法分析与设计实验报告

河北工业大学算法分析与设计2016实验报告学院:计算机科学与软件学院班级:姓名:学号:实验一【实验学时】4学时【实验目的】1．深刻理解并掌握“分治算法”的设计思想；2．提高应用“分治算法”设计技能；3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。【问题描述】设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次;（3）循环赛一共进行n-1天.按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时。【源程序】#includestdio.h#includemath.hvoidGameTable(intk,inta[80][80]){intn=2;inti,j,t,temp;a[1][1]=1;a[1][2]=2;a[2][1]=2;a[2][2]=1;for(t=1;tk;t++){temp=n;n=n*2;for(i=temp+1;i=n;i++)for(j=1;j=temp;j++)a[i][j]=a[i-temp][j]+temp;for(i=1;i=temp;i++)for(j=temp+1;j=n;j++)a[i][j]=a[i+temp][j-temp];for(i=temp+1;i=n;i++)for(j=temp+1;j=n;j++)a[i][j]=a[i-temp][j-temp];}}intmain(){inti,j,k;inta[80][80];printf(请输入k的数值k=);scanf(%d,&k);GameTable(k,a);for(i=1;i=pow(2,k);i++){for(j=1;j=pow(2,k);j++)printf(%5d,a[i][j]);printf(\n);}return0;}【运行结果】【分析总结】本次实验思路简单，并且编程实现也不复杂。通过这次试验，我对于分治法的设计思想理解地更加深入。其主要思想就是将一个大问题，分解为一个个的小问题，知道每个小问题很容易求出解为止。最后再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出元问题的解。实验二【实验学时】4学时【实验目的】（1）熟练掌握动态规划思想及教材中相关经典算法。（2）掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求解0/1背包问题。【问题描述】0/1背包问题是给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。【源程序】//本程序的测试用例是课本上的例题#includestdio.hintx[100],V[100][100];intmax(inta,intb){return(ab?a:b);}intKnapSack(intw[],intv[],intn,intC){inti,j;//初始化第0列for(i=0;i=n;i++)V[i][0]=0;//初始化第0行for(j=0;j=C;j++)V[0][j]=0;//双重for循环完成填表过程for(i=1;i=n;i++)for(j=1;j=C;j++)if(jw[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);//从右下角开始往回寻找for(j=C,i=n;i0;i--){if(V[i][j]V[i-1][j]){x[i]=1;j-=w[i];}elsex[i]=0;}//返回背包最大价值returnV[n][C];}intmain(){//n是物品个数；C是背包总容量intw[100],v[100],n,C;printf(请输入物品种类：);scanf(%d,&n);printf(请输入背包重量：);scanf(%d,&C);printf(请输入重量矩阵：);for(inti=1;i=n;i++)scanf(%d,&w[i]);//这里注意i从1开始取值printf(请输入价值矩阵：);for(inti=1;i=n;i++)scanf(%d,&v[i]);//这里注意i从1开始取值printf(\n);printf(背包取得的最大价值为：%d\n,KnapSack(w,v,n,C));printf(问题的最优解序列为：);for(inti=1;i=n;i++)printf(%2d,x[i]);printf(\n\n);printf(二维矩阵V为:\n);for(inti=0;i=n;i++){for(intj=0;j=C;j++)printf(%3d,V[i][j]);printf(\n);}return0;}【运行结果】【分析总结】通过这次试验，我体会到了动态规划法设计思想的巧妙之处。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，都希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。实验三【实验学时】6学时【实验目的】掌握贪心算法求解问题的一般特征和步骤；通过使用贪心算法求解0/1背包和TSP问题，进一步加深对贪心算法的理解和运用。【问题描述】0/1背包问题是给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量。因此背包问题具有最优子结构性质。TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。【0/1背包源程序】//本程序的测试用例来源于课本例题#includestdio.h#includealgorithmusingnamespacestd;structG{doublev;doublew;doublex=0;intflag=0;}good[100];boolcmp1(Ga,Gb)//按照性价比降序排序{returna.v/a.wb.v/b.w;}boolcmp2(Ga,Gb)//按照序号升序排序{returna.flagb.flag;}intmain(){inti,n,C;doublemaxValue=0;printf(请输入物品种类：);scanf(%d,&n);printf(请输入背包重量：);scanf(%d,&C);printf(请输入重量矩阵：);for(inti=0;in;i++){scanf(%lf,&good[i].w);good[i].flag=i;}printf(请输入价值矩阵：);for(inti=0;in;i++)scanf(%lf,&good[i].v);sort(good,good+n,cmp1);for(i=0;good[i].w=C;i++){good[i].x=1;maxValue+=good[i].v;C-=good[i].w;}good[i].x=(double)C/good[i].w;maxValue+=good[i].x*good[i].v;printf(背包的最大价值为:%.2f\n,maxValue);sort(good,good+n,cmp2);printf(问题的最优解向量为：);for(inti=0;in;i++){printf(%.1f,good[i].x);}printf(\n);return0;}【运行结果】【TSP源程序】#includestdio.h//#defineLOCALintarc[10][10];intn;//城市个数intw;//起点城市intTSP(intn,intw){intedgeCount=0,TSPLength=0;intmin=100,u,v;intflag[10]={0};//可以对于flag数组中所有元素清零；u=w;flag[w]=1;while(edgeCountn-1){min=100;for(intj=1;j=n;j++){if(flag[j]==0&&arc[u][j]min){v=j;min=arc[u][j];}}TSPLength+=arc[u][v];flag[v]=1;edgeCount++;printf(%d--,u);u=v;}printf(%d--%d\n,v,w);return(TSPLength+arc[u][w]);}intmain(){#ifdefLOCALfreopen(data.in,r,stdin);freopen(data.out,w,stdout);#endif//LOCALprintf(请输入城市个数:);scanf(%d,&n);printf(请输入代价矩阵:\n);for(inti=1;i=n;i++)for(intj=1;j=n;j++){scanf(%d,&arc[i][j]);}printf(请输入起点城市:);scanf(%d,&w);printf(最短路径为：);printf(最小代价为:%d,TSP(n,w));return0;}【运行结果】【分析总结】通过这次试验，我更好地掌握了贪心法的设计思想。运用贪心法时，主要有以下步骤：1.建立数学模型来描述问题2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。实验四【实验学时】6学时【实验目的】掌握回溯法的设计思想；掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；考察回溯法求解问题的有效程度。【问题描述】给定n种物品和一背包。物品i的重量是wi0，其价值为vi0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。【0/1背包源程序】#includeiostreamusingnamespacestd;intn,c,bestp;//物品的个数，背包的容量，最大价值intp[100],w[100],x[100],bestx