算法课程设计.doc

课 程 设 计 报 告课程设计名称： 算法设计与分析 系 别 ： 三 系 学 生 姓 名： 张 乐 乐 班 级： 软 件 工 程 学 号： 20090307110 成 绩： 指 导 教 师： 秦 川 开课时间： 2011 学年 1 学期一、问题描述描述要解决的问题1. 普通背包问题。背包载重：M10物品重量：w16、w25、w35物品价值：p142、p225、p3302. 棋盘覆盖问题。 在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 二、 问题分析1.普通背包问题：按单位价值排序：A,B,C依次将单位价值大的装入： 装C： M余=10-3=7； 装B： M余=7-2=5； 装C： M余=5-5=0；2.棋盘覆盖问题：当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。 递归地使用这种分割，直至棋盘简化为棋盘11。a) 三、 建立数学模型（根据问题情况选择，不需要此步骤可不要）1. 普通背包问题。2.棋盘覆盖问题用二维数组board ，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：( size2 -1 ) / 3将这些三格板编号为1到( s i z e2-1 ) / 3。则将残缺棋盘三格板编号的存储在数组board 的对应位置中，这样输出数组内容就是问题的解。四、 算法设计1.普通背包问题：该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)贪心装载时，耗时主要用于与剩余载重比较(w i=mm)时间为O(n)；故该算法的时间复杂度为：O(n*logn+n)；记为： O(n*logn)；2.棋盘覆盖问题。 以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。 从以上例子还可以发现，当残缺方格在第1个子棋盘，用号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图所示），当残缺方格在第2个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。 五、 算法实现1.普通背包问题。float greedy_knapsack ( float M, float w , float p , float x ) / x 背包问题最优解, w 物品重量， P 物品价值 int n=w.length;float pp=0;float mmM; /pp计算当前总价值，mm背包剩余载重for( int i=1;i=n; i+ ) float ww i= p i / w i； /计算物品单位价值ww x i=0; /初始化Mergesort ( w , n ); /按单位价值将物品排序，便于贪心选择for( int i=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部分放入背包 return pp;2.棋盘覆盖问题。void chessboard(int tr,int tc,int dr,int dc,int size)if(size=1)return;/2*2int s; int t=tile_num+;/L型骨牌号 static int tile_num = 1;s=size/2;/分割棋盘if(drtr+s&dctc+s)/覆盖左上角子棋盘chessboard(tr,tc,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+s-1tc+s-1=t;/用L型骨架覆盖右下角chessboard(tr,tc,tr+s-1,tc+s-1,s);/覆盖其余方格if(dr=tc+s)/覆盖右上角子棋盘chessboard(tr,tc+s,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+s-1tc+s=t;/L型骨牌覆盖左下角chessboard(tr,tc+s,tr+s-1,tc+s,s);/覆盖其余方格if(dr=tr+s&dc=tr+s&dc=tc+s)/覆盖右下角子棋盘chessboard(tr+s,tc+s,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+stc+s=t;/用L型骨架覆盖左上角chessboard(tr+s,tc+s,tr+s,tc+s,s);/覆盖其余方格六、 测试分析1.普通背包问题。该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)贪心装载时，耗时主要用于与剩余载重比较(w i=mm)时间为O(n)；故该算法的时间复杂度为：O(n*logn+n)；记为： O(n*logn)；2棋盘覆盖问题。设T(k)是覆盖一个2k2k棋盘所需时间；则其满足如下递归方程：解此递归方程得： T(k)O(4k)，故该算法的时间复杂度为O(4k) 七、结论1. 普通背包问题：采用贪心算法的思想，贪心算法原理是通过局部最优来达到全局最优，采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定标准下），决策一旦做出，就不可再更改。2. 棋盘覆盖问题：采用分治算法的思想，分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格(这句话很重要)，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处（要理解这句话），如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。八、源程序1.普通背包问题。#includeiostream#includeusing namespace std;#define N 100 struct goods /定义商品类，每个商品有，商品名，重量，价值，是否装入背包等属性, /并且有相应的设置属性，和获取属性的方法 char name; float weight; float value; float inBackpack;int goodsNum;/商品数量float backpack_weight;/背包载重float backpack_value=0;/背包总价值goods goodsArrayN; /商品数组float good_valueN;/商品单位价值数组bool input()/输入商品、背包相关信息coutbackpack_weight;coutendl; cout输入商品数量N (0NgoodsNum;coutendl;for(int i=0;igoodsNum;i+) cout输入第i+1goodsArrayi.name;cingoodsArrayi.weight;cingoodsArrayi.value;goodsArrayi.inBackpack=0;return i=goodsNum?true:false;bool init_good_value()/初始化商品单位价值数组 for(int i=0;igoodsNum;i+) good_valuei=goodsArrayi.value/goodsArrayi.weight; return i=goodsNum?true:false;bool rank_good_value()/根据单位价值，对商品数组进行排序 float a; goods gd; for(int i=0;igoodsNum;i+) for(int j=i+1;jgoodsNum;j+) if(good_valueigood_valuej) a=good_valuej; good_valuej=good_valuei; good_valuei=a; gd=goodsArrayj; goodsArrayj=goodsArrayi; goodsArrayi=gd; return i=goodsNum?true:false; void outRank()/输出排序后的物品顺序 cout根据单位重量价值，由大到小，对物品排序:endl; for(int i=0;igoodsNum;i+) coutgoodsArrayi.namet; coutendl; cout*0 & i=goodsArrayi.weight) goodsArrayi.inBackpack=goodsArrayi.weight; back_surWeight-=goodsArrayi.weight; backpack_value+=goodsArrayi.value; else goodsArrayi.inBackpack=back_surWeight; backpack_value+=good_valuei*back_surWeight; back_surWeight=0; i+; if(back_surWeight=0|i=goodsNum) c=true; return c;void output()/输出背包内物品 cout* START *endl; cout商品名t重量t价值endl; for(int i=0;i0) coutgoodsArrayi.nametgoodsArrayi.inBackpackt goodsArrayi.inBackpack*good_valueiendl; cout*endl; cout背包总价值为：backpack_valueendl; cout* END *endl;int main() if(input() cout商品信息输入完成!endl; cout*endl; if(init_good_value() if(rank_good_value() outRank(); if(putInBackpack() cout物品已装入背包!信息如下：endl; output(); else cout物品装入背包失败!endl; else cout根据单位重量价值，由大到小，对物品排序失败!endl; else cout初始化商品单位价值数组失败!endl; else cout商品信息录入失败!endl;return 1;2.棋盘覆盖问题。#include#includeiostream#define SIZE 4using namespace std;int boardSIZESIZE;int tile_num=1;/tr,tc:棋盘左上角的行号和列号/dr,dc:特殊方格的行号和列号/size=2kvoid chessboard(int tr,int tc,int dr,int dc,int size)if(size=1)return;/2*2int s; int t=tile_num+;/L型骨牌号 static int tile_num = 1;s=size/2;/分割棋盘if(drtr+s&dctc+s)/覆盖左上角子棋盘chessboard(tr,tc,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+s-1tc+s-1=t;/用L型骨架覆盖右下角chessboard(tr,tc,tr+s-1,tc+s-1,s);/覆盖其余方格if(dr=tc+s)/覆盖右上角子棋盘chessboard(tr,tc+s,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+s-1tc+s=t;/L型骨牌覆盖左下角chessboard(tr,tc+s,tr+s-1,tc+s,s);/覆盖其余方格if(dr=tr+s&dc=tr+s&dc=tc+s)/覆盖右下角子棋盘chessboard(tr+s,tc+s,dr,dc,s);/特殊方格在此棋盘中else/此棋盘中无特殊方格boardtr+stc+s=t;/用L型骨架覆盖左上角chessboard(tr+s,tc+s,tr+s,tc+s,s);/覆盖其余方格void output()/输出覆盖的棋盘 for(int tr = 0; tr SIZE; tr+) for(int tc = 0; tc SIZE; tc+) printf(%-4d, boardtrtc); printf(n); int main()int tr,tc;couttrtc; boardtr-1tc-1 = 0; chessboard(0, 0, tr-1, tc-1, SIZE); output(); return 1;九、参考文献（6个）算法设计与分析郑宗汉, 郑晓明编著，清华大学出版社，2005c+程序设计与分析马瑞新 等编著/2007-03-01/大连理工大学出版社算法设计方法吴哲辉等编著/2008-10-01/机械工业出版社c+程序设计与分析（美）维斯 著/2006-11-01/人民邮电出版社