算法分析报告与设计课设

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

1、成绩评定表学生姓名班级学号专业课程设计题目动态规划-k乘积问题回溯法-最小重量机器问题评语组长签字：成绩日期20年月日课程设计任务书学院专业学生姓名班级学号课程设计题目动态规划-k乘积问题回溯法-最小重量机器问题实践教学要求与任务:要求：1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2．培养学生自学参考书籍，查阅手册、和文献资料的能力。3．通过实际课程设计，掌握利用动态规划算法、回溯法、分支限界法等算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4．了解与课程有关的知识，能正确解释和分析实验结果。任务：按照算法设

2、计方法和原理，设计算法，编写程序并分析结果，完成如下内容：1.运用动态规划算法求解k乘积问题。2.运用回溯法求解最小重量机器问题。工作计划与进度安排:第11周：查阅资料。掌握算法设计思想，进行算法设计。第12周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法

3、更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。动态规划的基本思想与分治法类似，也是将待求解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规划中的子问题往往不是相互独立的，而是彼此之间有影响，因为有些子问题可能要重复计算多次，所以利用动态规划使这些子问题只计算一次。回溯法在用来求问题的所

4、有解时，要回溯到根，且根结点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统地搜索问题解的回溯算法，它适用于解决一些类似n皇后问题等求解方案问题，也可以解决一些最优化问题。在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。关键词：算法；动态规划；回溯法；目录一、问题描述11.1k乘积问题11.2最小重量机器问题1二、算

5、法设计1三、设计原理23.1动态规划23.2回溯法2四、问题分析与设计34.1k乘积问题34.2最小重量机器设计问题4五、算法实现45.1k乘积问题45.2最小重量机器问题7六、结果分析10总结11参考文献12一、问题描述1.1k乘积问题设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积，试设计一个算法，对于给定的I和k，求出I的最大k乘积。1.2最小重量机器问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不

6、超过c的最小重量机器设计。二、算法设计1.对于给定的I和k,计算I的最大k乘积。2.对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。12三、设计原理3.1动态规划动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.2回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度

7、优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。12四、问题分析与设计4.1k乘积问题1.分析最优解的结构为了方便起见，设I(s,t)是I的由s位开