《算法分析与设计课程设计报告》由会员分享，可在线阅读，更多相关《算法分析与设计课程设计报告（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;
