收藏 分销(赏)

算法课程设计.doc

上传人:天**** 文档编号:4655892 上传时间:2024-10-08 格式:DOC 页数:15 大小:3.71MB 下载积分:8 金币
下载 相关 举报
算法课程设计.doc_第1页
第1页 / 共15页
算法课程设计.doc_第2页
第2页 / 共15页


点击查看更多>>
资源描述
课 程 设 计 报 告 课程设计名称: 算法设计与分析 系 别 : 三 系 学 生 姓 名: 张 乐 乐 班 级: 软 件 工 程 学 号: 20090307110 成 绩: 指 导 教 师: 秦 川 开课时间: 2011 学年 1 学期 一、问题描述 描述要解决的问题 1. 普通背包问题。 背包载重:M=10 物品重量:w1=6、w2=5、w3=5 物品价值:p1=42、p2=25、p3=30 2. 棋盘覆盖问题。 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 二、 问题分析 1.普通背包问题: ①按单位价值排序:A,B,C ②依次将单位价值大的装入: 装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[ ][ ],模拟棋盘。覆盖残缺棋盘所需要的三格板数目为:( 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 mm=M; //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*2 int s; int t=tile_num++;//L型骨牌号 static int tile_num = 1; s=size/2;//分割棋盘 if(dr<tr+s&&dc<tc+s)//覆盖左上角子棋盘 { chessboard(tr,tc,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s-1][tc+s-1]=t;//用L型骨架覆盖右下角 chessboard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格 } if(dr<tr+s&&dc>=tc+s)//覆盖右上角子棋盘 chessboard(tr,tc+s,dr,dc,s);//特殊方格在此棋盘中 else{//此棋盘中无特殊方格 board[tr+s-1][tc+s]=t;//L型骨牌覆盖左下角 chessboard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格 } if(dr>=tr+s&&dc<tc+s)//覆盖左下角子棋盘 { chessboard(tr+s,tc,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s][tc+s-1]=t;//用L型骨架覆盖右上角 chessboard(tr+s,tc,tr+s,tc+s-1,s);//覆盖其余方格 } if(dr>=tr+s&&dc>=tc+s)//覆盖右下角子棋盘 { chessboard(tr+s,tc+s,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s][tc+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)是覆盖一个2k×2k棋盘所需时间;则其满足如下递归方程: 解此递归方程得: T(k)=O(4k),故该算法的时间复杂度为O(4k) 七、结论 1. 普通背包问题:采用贪心算法的思想,贪心算法原理是通过局部最优来达到全局最优,采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的(在一定标准下),决策一旦做出,就不可再更改。 2. 棋盘覆盖问题:采用分治算法的思想,分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格(这句话很重要),从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘,由于棋盘只有一个特殊棋盘,所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘,以便采用递归的方法求解,可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处(要理解这句话),如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略,直至将棋盘分割为1*1的子棋盘。 八、源程序 1.普通背包问题。 #include"iostream" #include<stdio.h> using 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 goodsArray[N]; //商品数组 float good_value[N];//商品单位价值数组 bool input()//输入商品、背包相关信息 { cout<<"输入背包载重:"; cin>>backpack_weight; cout<<endl; cout<<"输入商品数量N (0<N<=100):"; cin>>goodsNum; cout<<endl; for(int i=0;i<goodsNum;i++) { cout<<"输入第"<<i+1<<"个商品的信息(商品名 重量 价值):"; cin>>goodsArray[i].name; cin>>goodsArray[i].weight; cin>>goodsArray[i].value; goodsArray[i].inBackpack=0; } return i==goodsNum?true:false; } bool init_good_value()//初始化商品单位价值数组 { for(int i=0;i<goodsNum;i++) { good_value[i]=goodsArray[i].value/goodsArray[i].weight; } return i==goodsNum?true:false; } bool rank_good_value()//根据单位价值,对商品数组进行排序 { float a; goods gd; for(int i=0;i<goodsNum;i++) for(int j=i+1;j<goodsNum;j++) { if(good_value[i]<good_value[j]) { a=good_value[j]; good_value[j]=good_value[i]; good_value[i]=a; gd=goodsArray[j]; goodsArray[j]=goodsArray[i]; goodsArray[i]=gd; } } return i==goodsNum?true:false; } void outRank()//输出排序后的物品顺序 { cout<<"根据单位重量价值,由大到小,对物品排序:"<<endl; for(int i=0;i<goodsNum;i++) { cout<<goodsArray[i].name<<'\t'; } cout<<endl; cout<<"**************************************************"<<endl; } bool putInBackpack()//将物品装入背包 { bool c=false; int back_surWeight=backpack_weight,i=0; while(back_surWeight>0 && i<goodsNum){ if(back_surWeight>=goodsArray[i].weight) { goodsArray[i].inBackpack=goodsArray[i].weight; back_surWeight-=goodsArray[i].weight; backpack_value+=goodsArray[i].value; } else { goodsArray[i].inBackpack=back_surWeight; backpack_value+=good_value[i]*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;i<goodsNum;i++) { if(goodsArray[i].inBackpack>0){ cout<<goodsArray[i].name<<'\t'<<goodsArray[i].inBackpack<<'\t' <<goodsArray[i].inBackpack*good_value[i]<<endl; } } cout<<"**************************************************"<<endl; cout<<"背包总价值为:"<<backpack_value<<endl; 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<stdio.h> #include"iostream" #define SIZE 4 using namespace std; int board[SIZE][SIZE]; int tile_num=1; //tr,tc:棋盘左上角的行号和列号 //dr,dc:特殊方格的行号和列号 //size=2^k void chessboard(int tr,int tc,int dr,int dc,int size) { if(size==1)return;//2*2 int s; int t=tile_num++;//L型骨牌号 static int tile_num = 1; s=size/2;//分割棋盘 if(dr<tr+s&&dc<tc+s)//覆盖左上角子棋盘 { chessboard(tr,tc,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s-1][tc+s-1]=t;//用L型骨架覆盖右下角 chessboard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格 } if(dr<tr+s&&dc>=tc+s)//覆盖右上角子棋盘 chessboard(tr,tc+s,dr,dc,s);//特殊方格在此棋盘中 else{//此棋盘中无特殊方格 board[tr+s-1][tc+s]=t;//L型骨牌覆盖左下角 chessboard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格 } if(dr>=tr+s&&dc<tc+s)//覆盖左下角子棋盘 { chessboard(tr+s,tc,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s][tc+s-1]=t;//用L型骨架覆盖右上角 chessboard(tr+s,tc,tr+s,tc+s-1,s);//覆盖其余方格 } if(dr>=tr+s&&dc>=tc+s)//覆盖右下角子棋盘 { chessboard(tr+s,tc+s,dr,dc,s);//特殊方格在此棋盘中 } else{//此棋盘中无特殊方格 { board[tr+s][tc+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", board[tr][tc]); } printf("\n"); } } int main() { int tr,tc; cout<<"输入特殊方格的行列(tr tc):"; cin>>tr>>tc; board[tr-1][tc-1] = 0; chessboard(0, 0, tr-1, tc-1, SIZE); output(); return 1; } 九、参考文献(6个) 《算法设计与分析》郑宗汉, 郑晓明编著,清华大学出版社,2005 《c++程序设计与分析》马瑞新 等编著/2007-03-01/大连理工大学出版社 《算法设计方法》吴哲辉 等编著/2008-10-01/机械工业出版社 《c++程序设计与分析》(美)维斯 著/2006-11-01/人民邮电出版社
展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 学术论文 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服