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

课 程 设 计 报 告课程设计名称： 算法设计与分析系 ： 三系 学生姓名： 吴 阳 班 级： 12软件(2)班 学 号： 20120311232 成 绩： 指导教师： 秦川 开课时间： 2014 学年 一 学期一、问题描述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背包问题采