《算法分析与设计课程设计报告》由会员分享,可在线阅读,更多相关《算法分析与设计课程设计报告(27页珍藏版)》请在金锄头文库上搜索。
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八、参考文献26一、问题描述1、普通背包问题有一个背包容量为C,输入N个物品,每个物品有重量Si,以及物品放入背包中所得的收益Pi。求选择放入的物
2、品,不超过背包的容量,且得到的收益最好。物品可以拆分,利用贪心算法解决。2、0-1背包问题在0/1背包问题中,需对容量为c的背包进行装载。从n个物品中选取装入背包的物品,每件物品i的重量为wi, 价值为pi。对于可行的背包装载,背包中的物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即 取得最大值。约束条件 =c和 。在这个表达式中,需求出xi的值。xi=1表示物品i装入背包中,xi=0表示物品i不装入背包。3、棋盘覆盖问题在一个2k2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L
3、型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何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)问题分解过程如下: 以k=2时的问题为例,用二分法进行
8、分解,得到的是如下图4-8,用双线划分的四个k=1的棋盘。但要注意这四个棋盘,并不都是与原问题相似且独立的子问题。因为当如图4-8中的残缺方格在左上部时,第1个子问题与原问题相似,而右上角、左下角和右下角三个子棋盘(也就是图中标识为2、3、4号子棋盘),并不是原问题的相似子问题,自然也就不能独立求解了。当使用一个号三格板(图中阴影)覆盖2、3、4号三个子棋盘的各一个方格后,如4-8右图所示,我们把覆盖后的方格,也看作是残缺方格(称为“伪”残缺方格),这时的2、3、4号子问题就是独立且与原问题相似的子问题了。 图4.2 图4.3从以上例子还可以发现,当残缺方格在第1个子棋盘,用号三格板覆盖其余三
9、个子棋盘的交界方格,可以使另外三个子棋盘转化为独立子问题;同样地(如下图4-9所示),当残缺方格在第2个子棋盘时,则首先用号三格板进行棋盘覆盖,当残缺方格在第3个子棋盘时,则首先用号三格板进行棋盘覆盖,当残缺方格在第4个子棋盘时,则首先用号三格板进行棋盘覆盖,这样就使另外三个子棋盘转化为独立子问题。 如下图4.4所示:图4.42)棋盘的识别: 棋盘的规模是一个必要的信息,有了这个信息,只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了,残缺方格或“伪”残缺方格直接用行、列号记录。 tr 棋盘中左上角方格所在行。 tc 棋盘中左上角方格所在列。 dr 残缺方块所在行。 dl 残缺方块
10、所在列。 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; /物品价值double unit
11、_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=Pricej+1;Pricej+1=t
12、emp1; 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(); /按单位价值将物品排序,便于贪心选择 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;