算法设计与分析课程设计报告

课程设计报告课程设计名称：算法设计与分析系：三系学生姓名：吴阳班级：12软件(2)班学号：20120311232成绩：指导教师：秦川开课时间：2014学年一学期一、问题描述1．普通背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。2．0/1背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，对于每种物品i只有两种选择，即装入背包或者不装入背包，不能将物品装入背包多次，也不能只装入部分的物品i。3．棋盘覆盖问题在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。二、问题分析1．普通背包问题对于背包问题，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量Ｗ，剩余的将是n-1个原重物品1，2，······，j-1，j+1，·····，n以及重为Ｗi－Ｗ的物品j中可装入容量为C－Ｗ的背包且具有最大价值的物品。2．0/1背包问题如果当前背包中的物品的总容量是cw，前面的k-1件物品都已经决定好是否要放入包中，那么第k件物品是否放入包中取决于不等式cw+wk=M(其中，wk为第k件物品的容量，M为背包的容量)（此即约束条件）然后我们再寻找限界函数，这个问题比较麻烦，我们可以回忆一下背包问题的贪心算法，即物品按照物品的价值/物品的体积来从大到小排列，然后最优解为（1，1，1.......，1，t，0，0，......），其中0=t=1；因此，我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下)，我们可以考虑我们能够达到的最大的价值，即我们可以通过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。通过该条件，可以减去很多的枝条，大大节省运行时间。3．棋盘覆盖问题每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量s来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount来记录L型骨牌的数量。三、建立数学模型1．普通背包问题普通背包问题的数学描述为：在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。C0,wi0,vi0,1≤i≤n,要求找出一个n元0-1向量（x1,x2,x3,·····，xn）,xi∈{0,1}，1≤i≤n,使得niwixi1≤C,而且nxi1ivi达到最大。2．0/1背包问题0-1背包问题的数学描述为：不能将物品装入背包多次，也不能只装入部分的物品i。C0,wi0,vi0,1≤i≤n,要求找出一个n元0-1向量（x1,x2,x3,·····，xn）,xi∈{0,1}，1≤i≤n,使得niwixi1≤C,而且nxi1ivi达到最大。3．棋盘覆盖问题当k0时，将2k×2k棋盘分割为4个2^k-1×2^k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。四、算法设计1．普通背包问题因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解决。算法设计：首先计算每种物品单位重量的价值Vi/Wi，然后按单位重量价值从大到小进行排序，根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。或将这种物品全部装入背包后，背包内的物品总重量未超过背包容量C，则选择单位重量价值次高的物品并尽可能多地装入背包，依此策略一直进行下去，直到背包装满为止。2．0/1背包问题该0-1背包问题采用的是回溯算法，回溯算法的基本解题步骤是：（1）针对所给问题定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。算法设计：a.物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；b.用递归函数Backtrack(i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）：①若in，则算法搜索到一个叶结点，判断当前总价值是否最优：1若cpbestp，更新当前最优总价值为当前总价值（即bestp=cp），更新装载方案（即bestx[i]=x[i](1≤i≤n)）；②采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：1x[i]=j；2若总重量不大于背包容量（即cw+x[i]*w[i]=c），则更新当前总价br=值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）,对物品i+1调用递归函数Backtrack(i+1,cp,cw)继续进行装载；3函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量（即cw-=w[i]*x[i],cp-=p[i]*x[i]）；4当j1时，for循环结束；③当i=1时，若已测试完所有装载方案，外层调用就全部结束；c.主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。3．棋盘覆盖问题该棋盘算法用的是分治算法，分治法解题的思路就是将大问题化为若干子问题，再依次解决子问题，最后获得问题的答案。算法设计：（1）ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进行覆盖。（2）main()函数用来进行输入棋盘的大小和特殊棋盘的位置。（3）使用memset(Matrix,0,sizeof(Matrix))将Matrix[]数组清零。五、算法实现1．普通背包问题#includestdio.hstructgoodinfo{floatp;//物品价值floatw;//物品重量floatx;//物品该放数量intflag;//物品编码};voidInsertionsort(goodinfogoods[],intn){inti,j;for(j=2;j=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].pgoods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益重量比值做降序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i=n;i++)goods[i].x=0;cu=M;for(i=1;i=n;i++){if(goods[i].wcu)break;//当物品重量大于剩余容量时跳出goods[i].x=1;cu=cu-goods[i].w;//确定背包新的剩余容量}if(i=n){goods[i].x=cu/goods[i].w;//该物品所要放的量}//按物品编号做降序排列for(j=2;j=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].flaggoods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}printf(最优解为：\n);for(i=1;i=n;i++){printf(第%d件物品要放:%f,goods[i].flag,goods[i].x);printf(\n);}}voidmain(){printf(-----------运用贪心算法求解普通背包问题-------------\n);intj,n;floatM;goodinfo*goods;while(j){printf(请输入物品的总数量:);scanf(%d,&n);goods=newstructgoodinfo[n+1];printf(请输入背包的最大容量:);scanf(%f,&M);printf(\n);for(inti=1;i=n;i++){goods[i].flag=i;printf(请输入第%d个物品的重量：,i);scanf(%f,&goods[i].w);printf(请输入第%d个物品的价值：,i);scanf(%f,&goods[i].p);goods[i].p=goods[i].p/goods[i].w;printf(\n);}Insertionsort(goods,n);bag(goods,M,n);printf(如果继续则选择“1”，如果结束则选择“0”\n);scanf(%d,&j);}}2．0/1背包问题#includestdio.hintn,c,bestp;//物品的个数，背包的容量，最大价值intp[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况voidBacktrack(inti,intcp,intcw){//cw当前包内物品重量，cp当前包内物品价值intj;if(in)//回溯结束{if(cpbestp){bestp=cp;for(i=0;i=n;i++)bestx[i]=x[i];}}elsefor(j=0;j=1;j++){x[i]=j;if(cw+x[i]*w[i]=c){cw+=w[i]*x[i];cp+=p[i]*x[i];Backtrack(i+1,cp,cw);cw-=w[i]*x[i];cp-=p[i]*x[i];}}}intmain(){inti;bestp=0;printf(请输入背包最大容量:\n);scanf(%d,&c);printf(请输入物品个数:\n);scanf(%d,&n);printf(请依次输入物品的重量:\n);for(i=1;i=n;i++)scanf(%d,&w[i]);printf(请依次输入物品的价值:\n);for(i=1;i=n;i++)scanf(%d,&p[i]);Backtrack(1,0,0);printf(最大价值为:\n);printf(%d\n,bestp);printf(被选中的物品依次是(0表示未选中，1表示选中)\n);for(i=1;i=n;i++)printf(%d,bestx[i]);printf(\n);return0;}3．棋盘覆盖问题#includestdio.h#includestring.hintnCount=0;intMatrix[100][100];voidchessBoard(inttr,inttc,intdr,intdc,intsize);intmain(){printf(注意：矩阵大小为2的k次方!\n);inty=1;while(y){intsize,r,c,row,col;memset(Mat