算法设计与分析课程设计报告样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 课 程 设 计 报 告课程设计名称: 算法设计与分析系 : 三系 学生姓名: 吴 阳 班 级: 12软件(2)班 学 号: 0311232 成 绩: 指导教师: 秦川 开课时间: 年 一 学期一、 问题描述1普通背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1in。20/1背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3棋盘覆盖问题在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。二、 问题分析1普通背包问题对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量, 剩余的将是n-1个原重物品1, 2, , j-1, j+1, , n以及重为i的物品j中可装入容量为C的背包且具有最大价值的物品。20/1背包问题如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk = M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照 物品的价值/物品的体积 来从大到小排列, 然后最优解为( 1, 1, 1., 1, t, 0, 0, .) , 其中0=t0,wi0,vi0,1in,要求找出一个n元0-1向量( x1,x2,x3, xn) ,xi0,1, 1in,使得C,而且达到最大。20/1背包问题0-1背包问题的数学描述为: 不能将物品装入背包多次, 也不能只装入部分的物品i。 C0,wi0,vi0,1in,要求找出一个n元0-1向量( x1,x2,x3, xn) ,xi0,1, 1in,使得C,而且达到最大。3棋盘覆盖问题当k0时, 将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中, 其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘, 能够用一个L型骨牌覆盖这3个较小棋盘的会合处, 如 (b)所示, 从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割, 直至棋盘简化为棋盘11。四、 算法设计1普通背包问题因为每一个物品都能够分割成单位块, 单位块的利益越大显然总收益越大, 因此它局部最优满足全局最优, 能够用贪心法解决。算法设计: 首先计算每种物品单位重量的价值Vi/Wi, 然后按单位重量价值从大到小进行排序, 根据贪心选择策略, 将尽可能多的单位重量价值最高的物品装入背包。或将这种物品全部装入背包后, 背包内的物品总重量未超过背包容量C, 则选择单位重量价值次高的物品并尽可能多地装入背包, 依此策略一直进行下去, 直到背包装满为止。20/1背包问题该0-1背包问题采用的是回溯算法, 回溯算法的基本解题步骤是: ( 1) 针对所给问题定义问题的解空间; ( 2) 确定易于搜索的解空间结构; ( 3) 以深度优先方式搜索解空间, 并在搜索过程中用剪枝函数避免无效的搜索。算法设计: a.物品有n种, 背包容量为C, 分别用pi和wi存储第i种物品的价值和重量, 用xi标记第i种物品是否装入背包, 用bestxi存储第i种物品的最优装载方案; b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树( 形式参数i表示递归深度, n用来控制递归深度, 形式参数cp和cw表示当前总价值和总重量, bestp表示当前最优总价值) : 若i n, 则算法搜索到一个叶结点, 判断当前总价值是否最优: 1 若cpbestp, 更新当前最优总价值为当前总价值( 即bestp=cp) , 更新装载方案( 即bestxi=xi( 1in) ; 采用for循环对物品i装与不装两种情况进行讨论( 0j1) : 1 xi=j; 2 若总重量不大于背包容量( 即cw+xi*wi 值和总重量( 即cw+=wi*xi,cp+=pi*xi) , 对物品i+1调用递归函数Backtrack(i+1,cp,cw) 继续进行装载; 3 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量( 即 cw-=wi*xi,cp-=pi*xi) ; 4 当j1时, for循环结束; 当i=1时, 若已测试完所有装载方案, 外层调用就全部结束; c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程, 最终得到的bestp和bestxi即为所求最大总价值和最优装载方案。3棋盘覆盖问题该棋盘算法用的是分治算法, 分治法解题的思路就是将大问题化为若干子问题, 再依次解决子问题, 最后获得问题的答案。算法设计: ( 1) ChessBoard函数实现了递归的将棋盘划分为子棋盘, 并将棋盘进行覆盖。 ( 2) main()函数用来进行输入棋盘的大小和特殊棋盘的位置。 ( 3) 使用memset(Matrix,0,sizeof(Matrix)将Matrix数组清零。 五、 算法实现1普通背包问题#include struct goodinfofloat p;/物品价值float w;/物品重量float x;/物品该放数量int flag;/物品编码;void Insertionsort(goodinfo goods,int n)int i,j;for (j=2;jgoodsi.p )goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益重量比值做降序排列void bag(goodinfo goods,float M,int n)float cu;int i,j;for(i=1;i=n;i+)goodsi.x=0;cu=M;for(i=1;icu)break; /当物品重量大于剩余容量时跳出goodsi.x =1;cu=cu-goodsi.w ;/确定背包新的剩余容量if(i=n)goodsi.x =cu/goodsi.w ;/该物品所要放的量/按物品编号做降序排列for(j=2;j=n;j+)goods0=goodsj;i=j-1;while (goods0.flag goodsi.flag )goodsi+1=goodsi;i-;goodsi+1=goods0;printf(最优解为: n);for(i=1;i=n;i+)printf(第%d件物品要放: %f,goodsi.flag ,goodsi.x );printf(n);void main()printf(-运用贪心算法求解普通背包问题-n);int j,n;float M;goodinfo *goods;while (j)printf(请输入物品的总数量: );scanf(%d,&n);goods= new struct goodinfon+1;printf(请输入背包的最大容量: );scanf(%f,&M);printf(n);for (int i=1;i=n;i+)goodsi.flag =i;printf(请输入第%d个物品的重量: ,i);scanf(%f,&goodsi.w );printf(请输入第%d个物品的价值: ,i);scanf(%f,&goodsi.p );goodsi.p =goodsi.p /goodsi.w ;printf(n);Insertionsort(goods,n);bag(goods,M,n);printf(如果继续则选择”1”, 如果结束则选择”0”n);scanf(%d,&j);20/1背包问题#includeint n,c,bestp;/物品的个数, 背包的容量, 最大价值int p10000,w10000,x10000,bestx10000;/物品的价值, 物品的重量, xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包内物品重量, cp当前包内物品价值 int j; if(in)/回溯结束 if(cpbestp) bestp=cp; for(i=0;i=n;i+) bestxi=xi; else for(j=0;j=1;j+) xi=j; if(cw+xi*wi=c) cw+=wi*xi; cp+=pi*xi; Backtrack(i+1,cp,cw); cw-=wi*xi; cp-=pi*xi; int main() int i; bestp=0; printf(请输入背包最大容量:n); scanf(%d,&c); printf(请输入物品个数:n); scanf(%d,&n); printf(请依次输入物品的重量:n); for(i=1;i=n;i+) scanf(%d,&wi); printf(请依次输入物品的价值:n); for(i=1;i=n;i+) scanf(%d,&pi); Backtrack(1,0,0); printf(最大价值为:n); printf(%dn,bestp); printf(被选中的物品依次是(0表示未选中, 1表示选中)n); for(i=1;i=n;i+) printf(%d ,bestxi); printf(n); return 0;3棋盘覆盖问题#include #include int nCount = 0;int Matrix100100;void chessBoard(int tr, int tc, int dr, int dc, int size);int main()printf(注意: 矩阵大小为2的k次方!n);int y=1;while(y)int size,r,c,row,col;memset(Matrix,0,sizeof(Matrix);printf(请输入矩阵的大小:n);scanf(%d,&size);printf(请输入特殊矩阵的坐标:n);scanf(%d%d,&row,&col);chessBoard(0,0,row,col,size);for (r = 0; r size; r+)for (c = 0; c size; c+)printf(%2d ,Matrixrc);printf(n);printf(如果继续则按”1”, 退出则按”0”: );scanf(%d,&y); return 0;void chessBoard(int tr, int tc, int dr, int dc, int size) /覆盖左上角子棋盘 int s,t; if (1 = size) return; s = size/2; /分割棋盘 t = + nCount;/L型骨牌号 /特殊方格在此棋盘中 if (dr tr + s & dc tc +s) chessBoard(tr,tc,dr,dc,s); else Matrixtr+s-1tc+s-1 = t; chessBoard(tr,tc,tr+s-1,tc+s-1,s); /locate the special grid on bottom left corner if (dr = tc + s ) chessBoard(tr,tc+s,dr,dc,s); else Matrixtr+s-1tc+s = t; chessBoard(tr,tc+s,tr+s-1,tc+s,s); /locate the special grid on top right corner if (dr = tr + s & dc = tr + s & dc = tc + s) chessBoard(tr+s,tc+s,dr,dc,s); else Matrixtr+stc+s = t; chessBoard(tr+s,tc+s,tr+s,tc+s,s); 六、 测试分析1普通背包问题( 1) 输出结果( 2) 复杂度分析时间复杂度为O(nlgn)( 3) 问题及解决20/1背包问题( 1) 输出结果( 2) 复杂度分析计算上界需要O(n)时间, 在最坏的情况下有O(pow(2,n)个右儿子结点需要计算上界因此0-1背包问题的回溯算法所需的计算时间为O(*npow(2,n)。( 3) 问题及解决3棋盘覆盖问题( 1) 输出结果( 2) 复杂度分析设T( n) 是算法ChessBoard覆盖一个2k *2k棋盘所需要的时间, 则从算法的分治策略可知, T(k)满足如下递归方程: T(k)= k=0k0 解得此递归方程可得T(k) = O( 4k) 。由于覆盖一个2k *2k棋盘所需的L型骨牌个数为( 4k 1) /3,故算法ChessBoard是一个在渐进意义下最优的算法( 3) 问题及解决七、 结论1普通背包问题普通背包问题采用的是贪心算法。20/1背包问题0-1背包问题采用的是回溯算法3棋盘覆盖问题棋盘覆盖问题采用的是分治算法总结所解决的问题( 采用的什么算法, 怎么设计的, 还存在哪些问题有待改进等内容) 。八、 参考文献( 6个) 参考文献要注明作者、 出版社、 出版日期。如1 申俊龙著.新编医院管理教程M.北京: 科学出版社, : 25-163.2 Brian Henderson-Sellers. A Book of Object-Oriented Knowledge: An Introduction to Object-Oriented Software EngineeringM.Prentice-Hall, 1993: 39-113