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

《算法设计与分析课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程设计报告课程设计名称：算法设计与分析系别：三系学生姓名：班级：软件工程学号：成绩：指导教师：开课时间：2011学年1学期一、问题描述描述要解决的问题1.普通背包问题。背包载重：M＝10物品重量：w1＝6、w2＝5、w3＝5物品价值：p1＝42、p2＝25、p3＝302.棋盘覆盖问题。在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。二、问题分析1.普通背包问题：①按单位价值排序：A,B,C

2、②依次将单位价值大的装入：装C：M余=10-3=7；装B：M余=7-2=5；装C：M余=5-5=0；2.棋盘覆盖问题：当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。a)二、建立数学模型（根据问题情况选择，不需要此步骤可不要）1.普通背包问题。2.棋盘覆盖问题用二维数组board[][]，模拟棋盘。

3、覆盖残缺棋盘所需要的三格板数目为：(size2-1)/3将这些三格板编号为1到(size2-1)/3。则将残缺棋盘三格板编号的存储在数组board[][]的对应位置中，这样输出数组内容就是问题的解。三、算法设计1.普通背包问题：该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)贪心装载时，耗时主要用于与剩余载重比较(w[i]<=mm)时间为O(n)；故该算法的时间复杂度为：O(n*logn+n)；记为：O(n*logn)；2.棋盘覆盖问题。以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘

4、，并不都是与原问题相似且独立的子问题。因为当如图中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图所示），当残缺方

5、格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。二、算法实现1.普通背包问题。floatgreedy_knapsack(floatM,floatw[],floatp[],floatx[])//x[]背包问题最优解,w[]物品重量，P[]物品价值{intn=w.length;floatpp=0;floatmm＝M;//pp计算当前总价值，mm背包剩余载重for(inti=1;i<=n;i++){floatww[i]=p

6、[i]/w[i]；//计算物品单位价值ww[]x[i]=0;}//初始化Mergesort(w[],n);//按单位价值将物品排序，便于贪心选择for(inti=1;i<=n;i++)//贪心选择，总是选择价值最大放入背包{if(w[i]<=mm)//当前物品小于背包剩余载重{x[i]=1;mm=mm-w[i];pp=pp+p[i];}else{x[i]=mm/w[i];pp=pp+mm*w[i];break;}//i部分放入背包}returnpp;}2.棋盘覆盖问题。voidchessboard(inttr,inttc,intdr,intdc,intsize){if(size

7、==1)return;//2*2ints;intt=tile_num++;//L型骨牌号staticinttile_num=1;s=size/2;//分割棋盘if(dr