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

1、目 录一、问题描述11、普通背包问题12、0-1背包问题13、棋盘覆盖问题1二、问题分析21、普通背包问题22、0-1背包问题23、棋盘覆盖问题3三、算法设计31、普通背包问题32、0-1背包问题43、棋盘覆盖问题4四、算法实现61、普通背包问题62、0-1背包问题83、棋盘覆盖问题10五、测试分析111、普通背包问题112、0-1背包问题133、棋盘覆盖问题15六、结论16七、源程序171、普通背包问题172、0-1背包问题203、棋盘覆盖问题24八、参考文献2627 / 28文档可自由编辑打印一、问题描述1、普通背包问题有一个背包容量为C，输入N个物品，每个物品有重量Si，以及物品放入背包

2、中所得的收益Pi。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。2、0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi, 价值为pi。对于可行的背包装载，背包中的物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即 取得最大值。约束条件 =c和 。在这个表达式中，需求出xi的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。3、棋盘覆盖问题在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问

3、题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。二、问题分析1、普通背包问题贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。背包问题用贪心算法来解决，先求出每件物品的平均价值即pi/si，然后每次选择利润pi/si最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。2、0-1背包问题回溯法：是一个既带有系统性又带有跳跃性的的搜索算法。其基本思想是在搜索尝试中找问题

4、的解，当不满足条件就”回溯”返回，尝试别的路径。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其原先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。利用回溯算法来解决0-1背包，首先是将可供选择的物品的个数输入程序，将物品排成一列，计算总物品的重量weight，然后输入背包的实际重量weight，如果背包的重量小于0或者大于物品的总重量weight，则判断输入的背包重量错误，否则开始顺序选取物品装入背包，假设已选取了前i

5、 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解。 因为回溯求解的规则是后进先出，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。 3、棋盘覆盖问题将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特

6、殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格；右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格；左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格；右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格。当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。三、算法设计1、普通背包问题1）基本思路：首先，按物品

7、单位价值由大到小将物品排序；(为了贪心选择准备)然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满为止；在向背包放置物品的过程中，如果正在考虑装入的物品不能全部放进去，则可以将物品的部分放入背包； 2）算法设计：用一维数组xn (xi1,2, ,n)，保存问题的解；weight存储物品重量; price存储物品价值。2、0-1背包问题1）基本思路：确定问题的解空间，并将解空间组织成易于搜索的子集树的形式；图4.1解空间树以深度优先的方式搜索整个解空间，遇到不满足约束要求的节点就回溯，沿另一个分支继续搜索；约束函数剪枝，不能超载，超载就回溯。3、棋盘覆盖问题1）问题分解过程如下： 以

8、k=2时的问题为例，用二分法进行分解，得到的是如下图4-8，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图4-8中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。 图4.2 图4.3从以上例子还可以发现，当残缺方格在第

9、1个子棋盘，用号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图4-9所示），当残缺方格在第2个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。 如下图4.4所示：图4.42）棋盘的识别： 棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。 tr 棋盘中左上角方格所在行。 tc 棋盘中左上角方格所在列。 dr

10、残缺方块所在行。 dl 残缺方块所在列。 size:棋盘的行数或列数3）数据结构设计：用二维数组board ，模拟棋盘。覆盖残缺棋盘所需要的三格板(L牌)数目为：( size2 -1 ) / 3；将这些三格板编号为1到( s i z e2-1 ) / 3。则将残缺棋盘三格板编号的存储在数组board 的对应位置中，这样输出数组内容就是问题的解。结合图4.4，理解算法。四、算法实现1、普通背包问题1）声明变量、函数/ 声明变量int N; /物品数量int M; /背包容量double XMAX; /背包问题最优解double WeightMAX; /物品重量 double PriceMAX;

11、/物品价值double unit_priceMAX; /物品单位价值double total_price; /背包总价值 /声明函数void Input(); /输入函数void Mergesort(); /排序void knapsack(); /背包装载int Output(); /结果输出。2）实现了按照价值密度的降序排列void Mergesort() double temp1,temp2,temp3; for(int i=1;iN;i+) for(int j=1;j=N-i;j+) if(unit_pricejunit_pricej+1) temp1=Pricej;Pricej=Pri

12、cej+1;Pricej+1=temp1; temp2=Weightj;Weightj=Weightj+1;Weightj+1=temp2; temp3=unit_pricej;unit_pricej=unit_pricej+1;unit_pricej+1=temp3; 3）求最大总价值void knapsack() for( int i=1;i=N; i+ ) /初始化Xi，所有物品没有放入背包unit_pricei=Pricei/Weighti; /计算物品单位价值unit_price X i=0; double left=M; /背包剩余载重 Mergesort(); /按单位价值将物品

13、排序，便于贪心选择 while(left!=0) for(int i=1;i=N;i+) /贪心选择，总是选择价值最大放入背包 if(Weightileft) /部分放入背包 Xi=left/Weighti; left=0; total_price=total_price+Pricei*Xi; 2、0-1背包问题1）声明变量、函数#define N 100 /最大物品数/声明变量double c; /背包容量int n; /物品数double wN; /物品重量数组double pN; /物品价值数组double cw; /当前重量double cp; /当前价值double bestp; /

14、当前最优价值int pathN; /当前最优路径int xN; /最佳装载/声明结构体Goodsstruct Goodsdouble weight; /物品重量double price; /总价值int id; /物品编号float unit_price; /物品单位价值;Goods goodsN=0,0,0,0;/声明函数void backtract(int i); /搜索解空间函数double bound(int i); /界限函数void Input(); /输入函数void Output(); /输出函数2) 搜索解空间函数/=搜索解空间=void backtract(int i)/到

15、达叶节点if(i=n) / i表示深度（层），in搜索到叶子节点bestp=cp;for(int j=0;jn;j+)xj=pathj;return;/搜索子树if(cw+wibestp) /当前的节点不合适时，跳到下一个结点pathi=0;backtract(i+1);3）界限函数：/= 限界函数,计算当前价值与剩余价值和=double bound(int i)double cleft=c-cw; / 剩余容量double bound=cp; / 当前物品价值/以物品单位重量价值递减的顺序装入物品while(i=n&wi cleft 跳出循环，背包装满,物品部分装入背包/装满背包if(i=n

16、)bound+=pi*cleft/wi;return bound; / 当前物品价值与剩余物品价值之和3、棋盘覆盖问题1）声明变量：/声明变量int title=1; /L型骨牌号int board6464; /二维数组board ，模拟棋盘/*tr 棋盘中左上角方格所在行。tc 棋盘中左上角方格所在列。dr 残缺方块所在行。dl 残缺方块所在列。size:棋盘的行数或列数*/2）棋盘覆盖分治实现：void chessBoard(int tr,int tc,int dr,int dc,int size)int s,t;if(size=1) return; /size:棋盘行数t=title+;

17、 /L型骨牌号s=size/2; / 分割棋盘/ 覆盖左上角子棋盘if(drtr+s & dctc+s) /特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s); else / 此棋盘中无特殊方格 boardtr+s-1tc+s-1=t; / 用 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; / 用 t 号L型骨牌覆盖左

18、下角 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; / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s); /覆盖其余方格 五、测试分析1、普通背包问题1）、输入物品个数N=3,如图6.1所示。图6.1输入物品数2）、输入背包容量M：10，如图6.2所示。图6.2输入背包容

19、量3）、输入各物品的大小或重量weight：6 、 5 、 5，如图6.3所示。图6.3输入物品重量4）、输入各物品的价值p：42、25、30，如图6.4所示。图6.4输入物品价值5）、显示背包装载结果，如图6.5所示。图6.5结果显示2、0-1背包问题1）、输入背包容量：10,如图6.6所示。图6.6输入背包容量2）、输入物品个数：3，如图6.7所示。图6.7输入物品数量3）、输入各物品重量：6 、 5 、 5，如图6.8所示。图6.8输入物品重量4）、输入各物品的价值：42、25、30，如图6.9所示。图6.9输入物品价值5）、显示背包装载结果，如图6.10所示。图6.10结果显示3、棋盘

20、覆盖问题1）、输入size：8，如图6.11所示。图6.11输入棋盘大小2）、输入特殊方块的位置:4 3，如图6.12所示。图6.12输入特殊方格位置3）显示棋盘覆盖结果，如图6.13所示。图6.13结果显示六、结论三个算法，普通背包问题是用的贪心算法设计的，0-1背包问题是用回溯算法实现的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。在最终完成的程序中：贪心算法求普通背包问题，基本上已经实现了主要的功

21、能；01背包问题也能实现主要功能，但一开始未使用到界限函数，后来才加上；在分治算法求棋盘覆盖问题时，也基本上实现了它的功能，但在输入时还有不足，需要人工输入2的指数幂，不够方便。而且界面不够友好，不能实现单步覆盖。不过，总的来说这次实践也是有一定收获的，至少对书中这三个算法的知识进行了巩固，自己更进一步地理解了这三个算法贪心算法：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解。回溯法：就是一种穷举搜索算法。通俗地讲：回溯法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法。在0-1背包问题中，为了提高搜索效率，避免一些无效的搜

22、索，则需要用限界函数bound()剪去得不到最优解的子树。分治法：分而治之。即将一个难以直接解决的大问题小规模化，待解出子问题解之后，将子问题解合并为该问题解。七、源程序1、普通背包问题#include #define MAX 100 /物品件数最大值/ 声明变量int N; /物品数量int M; /背包容量double XMAX; /背包问题最优解double WeightMAX; /物品重量 double PriceMAX; /物品价值double unit_priceMAX; /物品单位价值double total_price; /背包总价值 /声明函数void Input(); /输

23、入函数void Mergesort(); /排序void knapsack(); /背包装载int Output(); /结果输出 /=输入函数=void Input() int i; coutN; coutendl; coutM; coutendl; cout请输入各物体的大小或重量weight:endl; for(i=1;iWeighti; cout请输入各物体的价值price:endl; for(i=1;iPricei; coutendl;/=按照价值密度的降序排列=void Mergesort() double temp1,temp2,temp3; for(int i=1;iN;i+)

24、 for(int j=1;j=N-i;j+) if(unit_pricejunit_pricej+1) temp1=Pricej;Pricej=Pricej+1;Pricej+1=temp1; temp2=Weightj;Weightj=Weightj+1;Weightj+1=temp2; temp3=unit_pricej;unit_pricej=unit_pricej+1;unit_pricej+1=temp3; /=实现背包装载=void knapsack() for( int i=1;i=N; i+ ) /初始化Xi，所有物品没有放入背包unit_pricei=Pricei/Weigh

25、ti; /计算物品单位价值unit_price X i=0; double left=M; /背包剩余载重 Mergesort(); /按单位价值将物品排序，便于贪心选择 while(left!=0) for(int i=1;i=N;i+) /贪心选择，总是选择价值最大放入背包 if(Weightileft) /部分放入背包 Xi=left/Weighti; left=0; total_price=total_price+Pricei*Xi; /=结果输出=int Output() char ch; cout贪心算法实现背包装载结果为:endl; for(int i=1;i=N;i+) cou

26、t第i个物体大小: Weighti 物体价值: Pricei 物体价值密度: unit_pricei endl; coutendl; cout向量表示: ( ; for(i=1;i=N;i+) /输出背包问题最优解 coutXi ; cout)endl; cout背包的最优装载值为：total_priceendl; /背包所装载总价值 cout按Y或y继续操作，否则按任意键ch; return ch;/=主函数=void main() total_price=0; char ch;while(1)Input(); knapsack(); ch=Output(); if(ch=Y|ch=y)co

27、ntinue; else break;2、0-1背包问题#include using namespace std;#define N 100 /最大物品数/声明变量double c; /背包容量int n; /物品数double wN; /物品重量数组double pN; /物品价值数组double cw; /当前重量double cp; /当前价值double bestp; /当前最优价值int pathN; /当前最优路径int xN; /最佳装载/声明结构体Goodsstruct Goodsdouble weight; /物品重量double price; /总价值int id; /物品

28、编号float unit_price; /物品单位价值;Goods goodsN=0,0,0,0;/声明函数void backtract(int i); /搜索解空间函数double bound(int i); /界限函数void Input(); /输入函数void Output(); /输出函数/=输入物品数量、背包容量、各物品重量、各物品价值=void Input()int i;coutc;coutn;for( i=0;iwi; for(i=0;ipi;/=输出部分=void Output()int i;printf(*n);cout最优装载方案是：n;for(i=0;in;i+)if(

29、xi=1)cout第goodsi.id个物品放入 价值是goodsi.priceendl;coutn最多装载价值：bestpendl;void knapsack()int i,j;cw=0;cp=0;bestp=0;for(i=0;in;i+)goodsi.id=i+1;goodsi.weight=wi;goodsi.price=pi;goodsi.unit_price=pi/wi;/物品按单位重量从大到小排序for(i=0;in-1;i+)for(j=0;jn-1-i;j+)if(goodsj.unit_pricegoodsj+1.unit_price)Goods temp=0,0,0,0;

30、temp=goodsj;goodsj=goodsj+1;goodsj+1=temp;/重新给p、 w 赋值for(i=0;in;i+)pi=goodsi.price;wi=goodsi.weight;/初始化当前最优路径for(i=0;i=n) / i表示深度（层），in搜索到叶子节点bestp=cp;for(int j=0;jn;j+)xj=pathj;return;/搜索子树if(cw+wibestp) /当前的节点不合适时，跳到下一个结点pathi=0;backtract(i+1);/= 限界函数,计算当前价值与剩余价值和=double bound(int i)double cleft=

31、c-cw; / 剩余容量double bound=cp; / 当前物品价值/以物品单位重量价值递减的顺序装入物品while(i=n&wi cleft 跳出循环，背包装满,物品部分装入背包/装满背包if(i=n)bound+=pi*cleft/wi;return bound; / 当前物品价值与剩余物品价值之和/=主函数=void main()Input();knapsack();Output();3、棋盘覆盖问题#include #include #include /声明变量int title=1; /L型骨牌号int board6464; /二维数组board ，模拟棋盘/*tr 棋盘中左上角方格所在行。tc 棋盘中左上角方格所在列。dr 残缺方块所在行。dl 残缺方块所在列。size:棋盘的行数或列数*/void chessBoard(int tr,int tc,int dr,int dc,int size)int s,t;if(size=