西工大算法分析设计实验报告.doc

. . . .算法设计分析实验报告回溯算法Problem A、0-1背包问题描述： 需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。初始化的数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。void checkmax(int n,int c)int i, weight=0, value=0;for(i=0;in;i+)if(ai=1)weight = weight + wi;value = value + vi;if(weightmax) max=value;Problem B、装载问题描述： 有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。此题跟上题有异曲同工之处！其核心代码如下！void Sesearch(int m,int r_weight,int cw)int i=0;if(m=n)if(cw=bestcw&cw=c1)bestcw=cw;success=1;cw_weight=0;for(i=0;in;+i)if(ai)cw_weight+=bi;elseam=1;if(cw+bmbestcw)Sesearch(m+1,r_weight-bm+1,cw);Problem C、堡垒问题描述： 城堡是一个44的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。这个问题上课没听，下来问的同学，还是没搞的太明白！代码是找同学帮忙修改的！核心问题：void Sesearch(int m,int cw,int rw)if(m=ROW*COL)if(cwbestcw)bestcw=cw;elseif(am/COLm%ROW=2)Sesearch(m+1,cw,rw-1);elseif(canplace(m)am/COLm%COL=1;Sesearch(m+1,cw+1,rw-1);am/COLm%ROW=0;if(cw+rwbestcw)Sesearch(m+1,cw,rw-1);Problem D、8皇后问题描述： 输出8皇后问题所有结果。输出： 每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，A表示皇后，.表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。八皇后问题还是蛮有意思的，在听过老师上课讲解后，有了思路！但是c语言学的不好，有了思路还是花了不少时间来些代码!在同学的帮助下，完善了代码！核心算法：void sesearch(int m, int a8)int i;if(m=8)if(n3)output(a);+n;elsefor(i=0;i=0)&(row=0)&(col20)&arowcol=0)return 1;else return 0;int Search(int row,int col,int x,int y)int r,c;if(row=x)&(col=y)&arowcol=0)return 1;arowcol=1;r=row; /左c=col-1;if(Canplace(r,c) if(Search(r,c,x,y)return 1;r=row+1; /下c=col;if(Canplace(r,c)if(Search(r,c,x,y)return 1;r=row; /右c=col+1;if(Canplace(r,c)if(Search(r,c,x,y)return 1;r=row-1; /上c=col;if(Canplace(r,c)if(Search(r,c,x,y)return 1;int main()int i=0,j=0,n=0;int result11=0;scanf(%d,&n);while(in)Putin();resulti=Search(x0,y0,x,y);i+;for(j=0;j=1)printf(Yesn);elseprintf(Non);return 0;宁可累死在路上，也不能闲死在家里！宁可去碰壁，也不能面壁。是狼就要练好牙，是羊就要练好腿。什么是奋斗？奋斗就是每天很难，