《算法分析与设计课设》由会员分享，可在线阅读，更多相关《算法分析与设计课设（16页珍藏版）》请在金锄头文库上搜索。
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二、算法设计1三、设计原理23.1动态规划23.2
5、回溯法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是相应的价格。试设 计一个算法，给出总价格不超过c的最小重量机器设计。二、算法设计1. 对于给定的I和k,计
6、算I的最大k乘积。2. 对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机 器设计。三、设计原理3.1动态规划动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问 题得到原问题的解。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.2回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所 有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜 索至解空间树的任一结点时，总是先判断该结
7、点是否肯定不包含问题的解。如果 肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。 否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所 有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用 来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的 方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问 题。、问题分析与设计41k乘积问题1.分析最优解的结构为了方便起见，设I(s,t)是I的由s位开始的t位数字组成的十进制数，R(i,j)表示I(0,i)的j乘积。第j段的起始位置为第w位,1VwWj。则有如下
8、关系R(i,j) = R(i,j-1)XI(w,j-w)要使R(i,j)最大，则R(i,j-1)也是最大，所以最大K乘积问题的最优解包含其子问题的最优解。2.建立递归关系设MaxIij表示I(0,i)的最大j乘积，则原问题的最优值为MaxInk。当 k=1 时，MaxIn1 = I(0,n);当k尹1时，可利用最优子结构性质计算MaxInk,若计算MaxInk的第 k段的起始位置为第 w位，1VwWj，则有MaxInk = MaxIwk-1 X I(w,n-w)。 由于在计算时并不知道第k段的起始位置w，所以w还未定。不过w的值只有n-k+2 种可能，口 kTWwWn。所以MaxInk可以递归
9、地定义为I(0,n)k=1MaxInk = max MaxIwk-1 X I(w,n-w)k乂 1MaxInk给出了最优值，同时还确定了计算最优的断开位置w，也就时说， 对于这个 w 有 MaxInk = MaxIwk-1 X I(w,n-w)若将对应于MaxInk的断开位置w记为demarcationnk后，可递归地 由demarcationnk 构造相应的最优解。4.2最小重量机器设计问题1. 用递归函数backtrack(i)来实现回溯法搜索排列树(形式参数i表示递归深 度)。 若cpd，则为不可行解，剪去相应子树，返回到i-1层继续执行。 若cw=weight，则不是最优解，剪去相应子
10、树，返回到i-1层继续执行。 若in，则算法搜索到一个叶结点，用weight对最优解进行记录，返回到 i-1层继续执行； 用for循环对部件i从m个不同的供应商购得的情况进行选择(1WjWm)。2. 主函数调用一次backtrack(1)即可完成整个回溯搜索过程，最终得到的 weight即为所求最小总重量，p为该机器最小重量的价格。五、算法实现5.1k乘积问题#include#include#include#define MAXN 51#define MAXK 10/mij表示1i十进制位分成j段所得的最大乘积long mMAXKMAXN=0,0;/wij表示ij十进制位所组成的十进制数lon
11、g wMAXNMAXN=0,0;int leafMAXNMAXN = 0,0；void maxdp(int n,int k,int *a)int i,j,d;long temp,max;for(i=1; i= n; i+)分成一段mi1 = w1i;for(i=2 ; i= n ; i+)( /DP 过程for(j=2; j= k ; j+)max = 0;for(d=1; d max) max = temp ;leafij=d;mij = max ;printf(n);printf(n);for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%ldt”,mij);prin
12、tf(n);printf(n);for(i=1;i=n;i+)for(j=1;j 0) stacktop+ = tmp; k;printf(Divided sequence:n);i = 1;while (-top) = 0)tmp = stacktop;for ( ; i = tmp; i+)printf(%d”, datai);printf();for (; i = n; i+)printf(%d”, datai);printf(n);int main(void)int n,k,i,j;int aMAXN=0,la=0;char c ;scanf(%d %d ,&n,&k);/input
13、n, kwhile ( ( c=getchar() )!=#) /read integer a+la = c-0;for(i=1 ; i= n; i+)wii= ai;for(j=i+1 ; j= n; j+)wij = wij-1*10 + aj;for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%ldt”,wij);printf(n);maxdp(n,k,a);printf(%ldn,mnk);print_foot(a, n, k);return 0;5.2最小重量机器问题/*头文件最小重量机器设计问题.h*/#ifndef KNAP_H#define KNAP_H#include #include
