算法分析与设计课设

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

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

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

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

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

6、量和机器部件价格，计算总价格不超过d的最小重量机器设计。三、设计原理3.1动态规划动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值(写出动态规划方程)；(3)以自底向上的方式计算出最优值；(4)根据计算最优值时得到的信息，构造一个最优解。3.2回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以

7、该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。四、问题分析与设计4.1k乘积问题1 .分析最优解的结构为了方便起见，设I(s,t)是I的由s位开始的t位数字组成的十进制数，R(i,j)表示I(0,i)的j乘积。第j段的起始位置为第w位,1<w<j。则有如下关系R(i,j)=R(i,j-1)xI(w,j

8、-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位，1<w<j,则有MaxInk=MaxIwk-1xI(w,n-w)。由于在计算时并不知道第k段的起始位置w,所以w还未定。不过w的值只有n-k+2种可能，即k-1&w<n。所以MaxInk可以递归地定义为I(0,n)k=1MaxInk=max

9、MaxIwk-1xI(w,n-w)kw1MaxInk给出了最优值，同时还确定了计算最优的断开位置w,也就时说，对于这个w有MaxInk=MaxIwk-1xI(w,n-w)若将对应于MaxInk的断开位置w记为demarcationnk后，可递归地由demarcationnk构造相应的最优解。3 .2最小重量机器设计问题1.用递归函数backtrack(i)来实现回溯法搜索排列树(形式参数i表示递归深度)。若cp>d,则为不可行解，剪去相应子树，返回到i-1层继续执行。若cw>=weight,则不是最优解，剪去相应子树，返回到i-1层继续执行。若i>n,则算法搜索到一个叶结点，

10、用weight对最优解进行记录，返回到i-1层继续执行；用for循环对部件i从m个不同的供应商购得的情况进行选择(1&j&m,2.主函数调用一次backtrack(l)即可完成整个回溯搜索过程，最终得到的weight即为所求最小总重量，p为该机器最小重量的价格。五、算法实现5.1k乘积问题#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN51#defineMAXK10/mij表示1i十进制位分成j段所得的最大乘积longmMAXKMAXN尸0,0;/wij表示ij十

11、进制位所组成的十进制数longwMAXNMAXN=0,0;intleafMAXNMAXN=0,0;voidmaxdp(intn,intk,int*a)inti,j,d;longtemp,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<i;d+)/Testprintf("%d*%d=%ldt",mdj-1,wd+1i,mdj-1*wd+1i);if(temp=mdj-1*wd+1i)>max)max=temp;leafij=d

12、;mij=max;printf("n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%ldt",mij);printf("n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%ldt",leafij);printf("n");/输出分割后的K个数voidprint_foot(int*data,intn,intk)

13、intd,i;intstack256;inttop=0;inttmp;tmp=n;while(tmp=leaftmpk)>0)stacktop+=tmp;k-;printf("Dividedsequence: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");intmain(v

14、oid)intn,k,i,j;intaMAXN=0,la=0;charc;scanf("%d%d",&n,&k);/inputn,kwhile(c=getchar()!='#')/readintegera+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");max

15、dp(n,k,a);printf("%ldn",mnk);print_foot(a,n,k);return0;5.2最小重量机器问题/*头文件最小重量机器设计问题.h*/#ifndefKNAP_H#defineKNAP_H#include<iostream>#include<fstream>usingnamespacestd;classMachinepublic:Machine(char*in,char*out);Machine();voidSolve();protected:voidSearch(inti,ints,intl,int*e);void

16、Print();private:intn;intm;intd;int*w;int*c;intmin;int*plan;ofstreamfout;#endif/*函数实现文件最小重量机器设计问题.cpp*/#include"最小重量机器设计问题.h"Machine:Machine(char*in,char*out):fout(out)ifstreamfin(in);if(!fin)机器类/构造函数/析构函数/输出结果到文件/从第i个部件开始递归搜索/输出结果/部件个数/供应商个数/价格上限/部件重量/部件价格/最小重量/选购的部件/输出结果文件cerr<<&quo

17、t;文件"<<in<<"无法打开！"<<endl;exit(1);fin>>n>>m>>d;w=newint*n+1;/初始化部件个数n,供应商数m,价格限制dfor(inti=1;i<=n;i+)wi=newintm+1;for(intj=1;j<=m;j+)fin>>wij;c=newint*n+1;for(inti=1;i<=n;i+)ci=newintn+1;for(intj=1;j<=m;j+)fin>>cij;fin.close();

18、min=INT_MAX;plan=newintn+1;for(inti=1;i<=n;i+)plani=0;if(!fout)/初始化部件重量/初始化部件价格/初始化最小重量/初始化选购计划cerr<<"文件"<<out<<"无法打开！"<<endl;exit(1);Machine:Machine()if(fout)fout.close();for(inti=1;i<=n;i+)if(wi)delete口wi;if(ci)delete口ci;if(w)delete口w;if(c)delete口c

19、;voidMachine:Solve()int*e;e=newintn+1;for(inti=1;i<=n;i+)ei=0；Search。，0,0,e);第Print();voidMachine:Search(inti,ints,intl,int*e)if(i=n+1)if(s<min&&l<=d)min=s;for(inti=1;i<=n;i+)plani=ei;return;if(s>min)return;for(intj=1;j<=m;j+)ei=j;s+=w皿;1 +=c皿;Search(i+1,s,l,e);s-=wij;l-=ci

20、j;voidMachine:Print()fout<<min<<endl;for(inti=1;i<=n;i+)fout<<plani<<''/*主函数文件test.cpp*/#include"最小重量机器设计问题.h"intmain()char*in="input.txt"char*out="output.txt"Machinemachine(in,out);machine.Solve();个零件开始搜索，初始重量和价格是0输出函数/选购完毕/找到一个更优解/更新

21、重量最小值/更新选购计划/重量超过min,剪枝加上第i部件由j供应商提供的重量加上第i部件由j供应商提供的价格/递归选购下一个部件/输入文件/输出文件/文件初始化机器/回溯法求解return0;六、结果分析1.*'C；UseriAdministratorDe5ktop机房软件DubugCppl.exe"qa 0810010lasDivided sequence -5 21Pr-ess an u kgy tQ continue注释：输入一个三位数，将其分为两段，使这两端乘积最大当这个三位数为521时，5与21相乘积最大，为105二）回2.32GH243S126S口平谷口聿后口毛后口鼻口口聿1d-电32 34上 1!巨< 爰-7|FJ一！-/-lbJdT1 -: .-t:>wplkYlH 1ITT JTT -/Ff .tn .H .Is -in ITF JT A JftlArA JlTJ o 7J 4%" TJ TJ制.I" 口田用古口田都e7口用剖.1 -: 口金 s 6 3 3 1 6! kl 1X1X1 vlxlck 113233113