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

1、. .课 程 设 计 报 告课程设计名称：算法设计与分析系 ： 三系 学生XX： 阳班 级：12软件(2)班 学 号：成 绩：指导教师： 川 开课时间：2021学年一学期一、问题描述1普通背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，可以选择物品i的一局部，而不一定要全部装入背包，1in。20/1背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，对于每种物品i只有两种选

2、择，即装入背包或者不装入背包，不能将物品装入背包屡次，也不能只装入局部的物品i。 3棋盘覆盖问题在一个2k x 2k个格组成的棋盘中恰有一个格与其他的不同称为特殊格，想要求利用四种L型骨牌每个骨牌可覆盖三个格不相互重叠覆盖的将除了特殊格外的其他格覆盖。二、问题分析1普通背包问题对于背包问题，假设它的一个最优解包含物品j，那么从该最优解中拿出所含的物品j的那局部重量，剩余的将是n-1个原重物品1，2，······，j-1，j+1，·····，n以及重为i的物品j中可装入容量为C的背包且具

3、有最大价值的物品。20/1背包问题如果当前背包中的物品的总容量是cw，前面的k-1件物品都已经决定好是否要放入包中，那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中，wk为第k件物品的容量，M为背包的容量)此即约束条件 然后我们再寻找限界函数，这个问题比较麻烦，我们可以回忆一下背包问题的贪心算法，即物品按照 物品的价值/物品的体积 来从大到小排列，然后最优解为1，1，1.，1，t，0，0，.，其中0<=t<=1； 因此，我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下)，我们可以考虑我们能够到达的最大的价值，即我们可以通过计算

4、只放入一局部的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。通过该条件，可以减去很多的枝条，大大节省运行时间。3棋盘覆盖问题每次都对分割后的四个小块进展判断，判断特殊格是否在里面。这里的判断的法是每次先记录下整个大块的左上角格的行列坐标，然后再与特殊格坐标进展比较，就可以知道特殊格是否在该块中。如果特殊块在里面，这直接递归下去求即可，如果不在，这根据分割的四个块的不同位置，把右下角、左下角、右上角或者左上角的格标记为特殊块，然后继续递归。在递归函数里，还要有一个变量s来记录边的格数，每次对块进展划分时，边的格数都会减半，这个

5、变量是为了便判断特殊格的位置。其次还要有一个变nCount来记录L型骨牌的数量。三、建立数学模型1普通背包问题普通背包问题的数学描述为：在选择物品i装入背包时，可以选择物品i的一局部，而不一定要全部装入背包，1in。C>0,wi>0,vi>0,1in,要求找出一个n元0-1向量x1,x2,x3,·····，xn,xi0,1，1in,使得C,而且到达最大。20/1背包问题0-1背包问题的数学描述为：不能将物品装入背包屡次，也不能只装入局部的物品i。 C>0,wi>0,vi>0,1in,要求找出一个n元0-1向量

6、x1,x2,x3,·····，xn,xi0,1，1in,使得C,而且到达最大。3棋盘覆盖问题当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊格。为了将这3个无特殊格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。四、算法设计1普通背包问题因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越

7、大，所以它局部最优满足全局最优，可以用贪心法解决。算法设计：首先计算每种物品单位重量的价值Vi/Wi，然后按单位重量价值从大到小进展排序，根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。或将这种物品全部装入背包后，背包的物品总重量未超过背包容量C，那么选择单位重量价值次高的物品并尽可能多地装入背包，依此策略一直进展下去，直到背包装满为止。20/1背包问题该0-1背包问题采用的是回溯算法，回溯算法的根本解题步骤是： 1针对所给问题定义问题的解空间； 2确定易于搜索的解空间构造； 3以深度优先式搜索解空间，并在搜索过程中用剪枝函数防止无效的搜索。算法设计：a.物品有n种，背包容量为C

8、，分别用pi和wi存储第i种物品的价值和重量，用xi标记第i种物品是否装入背包，用bestxi存储第i种物品的最优装载案；b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值： 假设i >n，那么算法搜索到一个叶结点，判断当前总价值是否最优：1> 假设cp>bestp，更新当前最优总价值为当前总价值即bestp=cp，更新装载案即bestxi=xi( 1in)； 采用for循环对物品i装与不装两种情况进展讨论0j1：1> xi=j；2

9、> 假设总重量不大于背包容量即cw+xi*wi<=c，那么更新当前总价 br=""> 值和总重量即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> 当j>1时，for循环完毕； 当i=1时，假设已测试完所有装载案，外层调用就全部完毕；c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和b

10、estxi即为所求最大总价值和最优装载案。3棋盘覆盖问题该棋盘算法用的是分治算法，分治法解题的思路就是将大问题化为假设干子问题，再依次解决子问题，最后获得问题的答案。算法设计：1ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进展覆盖。 2 main()函数用来进展输入棋盘的大小和特殊棋盘的位置。 3使用memset(Matrix,0,sizeof(Matrix)将Matrix数组清零。 五、算法实现1普通背包问题#include <stdio.h>struct goodinfofloat p;/物品价值float w;/物品重量float x;/物品该放数量int

11、 flag;/物品编码;void Insertionsort(goodinfo goods,int n)int i,j;for (j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.p >goodsi.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;i<=n;i+)if(goodsi.w

12、>cu)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件物品要放:

13、 %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);p

14、rintf("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);prin

15、tf("如果继续那么选择“1，如果完毕那么选择“0n");scanf("%d",&j);20/1背包问题#include<stdio.h>int n,c,bestp;/物品的个数，背包的容量，最大价值int p10000,w10000,x10000,bestx10000;/物品的价值，物品的重量，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包物品重量，cp当前包物品价值 int j; if(i>n)/回溯完毕 if(cp>bestp) bestp=

16、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)

17、; 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(

18、i=1;i<=n;i+) printf("%d ",bestxi); printf("n"); return 0;3棋盘覆盖问题#include <stdio.h>#include <string.h>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,

19、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);prin

20、tf("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(t

21、r,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 < tr + s && dc >= 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 < tc + s) chessBoard(tr+s,tc,dr,dc,s); else Matrixtr+stc+s-1 = t; chessBoard(tr+s,tc,tr+s,tc+s-1,s); /locate the special grid on top left corner if (dr >= tr + s && dc >= tc + s) chessBoard