算法设计_课程设计

《算法设计_课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程设计名称：算法设计与分析系：计算机科学系学生姓名：班级：学号：成绩：指导教师：开课时间：2013-2014学年1学期一、问题描述1、普通背包装载问题有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决问题。2、0-1背包装载问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大3、棋盘覆盖问题在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方

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

3、：通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题定义解空间。这个解空间必须至少包含问题的一个解（可能是最优的），然后组织解空间，确定易于搜索的解空间结构后，按照深度优先策略从开始结点出发搜索解空间。并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树，用目标函数剪去得不到最优解的子树，避免无效搜索。0-1背包问题的数学描述为：n个物品，物品i的重量是wi、其价值为vi，其中0≤i≤n-1，背包的容量为C。用xi表示物品i被装入背包的情况，如果物品Pi被选中，则xi=1；否则xi=0。求满足目标函数和约束方程的物品组合（x0，x1，x2，…，xn-1)与相

4、应的总价值V。3、棋盘覆盖问题：分治算法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处（要理解这句话），如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为11的子棋盘。三、建立数学模型1、普通

5、背包问题：求平均价值即p[i]/s[i]约束条件：c1<=02、0-1背包装载问题：n个物品，物品i的重量是wi、其价值为vi，其中0≤i≤n-1，背包的容量为C。用x[i]表示物品i被装入背包的情况，如果物品Pi被选中，则xi=1；否则xi=0，用bestx[i]存储第i种物品的最优装载方案。求相应的总价值cw和总重量cp。约束条件：目标函数和约束方程3、棋盘覆盖问题：(1)棋盘：可以一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设置为全局变量(2)子棋盘：子棋盘由原始棋盘数组board的行下标tr，

6、列下标tc表示。(3)特殊方格：用board[dr][dc]表示特殊方格，dr和dc表示该特殊方格的在二维数组board中的下标(4)L型骨牌：一个（2^k）（2^k）的棋盘中有一个特殊方格，所以用到L型骨牌的个数为（4^k-1）/3，将所有L型骨牌从1开始连续编号，同一个骨牌有3个方格组成，这3个方格用同一个编号。四、算法设计1、普通背包装载问题：用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。intn物品个数doubleC背包的容量doubles[i]物品的重量（或大小）doub

7、lep[i]物品的价值voidaverage(intn,doubles[M],doublep[M])//按照价值密度的降序排列函数；doublec1背包剩余容量totalp物品的总价值voidbag(intn,doubleC,doubles[M],doublep[M],doublex[M])求物品总价值的函数在求物品总价值函数中要调用average函数，在主函数中调用bag()函数。2、0-1背包