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

《算法分析与设计课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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个物品，每个物品

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

3、格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。-26-算法分析与设计课程设计报告二、问题分析1、普通背包问题贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。背包问题用贪心算法来解决，先求出每件物品的平均价值即p[i]/s[i]，然后每次选择利润p[i]/s[i]最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。

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

5、于0或者大于物品的总重量weight，则判断输入的背包重量错误，否则开始顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"太大"不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明"刚刚"装入背包的那件物品"不合适"，应将它取出"弃之一边"，继续再从"它之后"的物品中选取，如此重复，直至求得满足条件的解。因为回溯求解的规则是"后进先出"-26-算法分析与设计课程设计报告，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符

6、合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。3、棋盘覆盖问题将2^kx2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格；右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格；左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格；右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格。当然上面四种，只可能且必定只有三个成立，那三个假设的

7、特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。三、算法设计1、普通背包问题1）基本思路：首先，按物品单位价值由大到小将物品排序；(为了贪心选择准备)然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满为止；-26-算法分析与设计课程设计报告在向背包放置物品的过程中，如果正在考虑装入的物品不能全部放进去，则可以将物品的部分放入背包；2）算法设计：用一维数组x[n](x