算法分析与设计课程设计-动态规划-k乘积问题回溯法-最小重量机器问题.docx

成绩评定表学生姓名班级学号专业课程设计题目动态规划-k乘积问题回溯法-最小重量机器问题评语组长签字：成绩日期20 年 月 日课程设计任务书学 院专 业学生姓名班级学号课程设计题目动态规划-k乘积问题 回溯法-最小重量机器问题实践教学要求与任务:要求：1巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。2培养学生自学参考书籍，查阅手册、和文献资料的能力。3通过实际课程设计，掌握利用动态规划算法、回溯法、分支限界法等算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。4了解与课程有关的知识，能正确解释和分析实验结果。任务：按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容：1.运用动态规划算法求解k乘积问题。2. 运用回溯法求解最小重量机器问题。工作计划与进度安排:第11周：查阅资料。掌握算法设计思想，进行算法设计。第12周：算法实现，调试程序并进行结果分析。撰写课程设计报告，验收与答辩。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘要为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。动态规划的基本思想与分治法类似，也是将待求解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规划中的子问题往往不是相互独立的，而是彼此之间有影响，因为有些子问题可能要重复计算多次，所以利用动态规划使这些子问题只计算一次。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统地搜索问题解的回溯算法，它适用于解决一些类似n皇后问题等求解方案问题，也可以解决一些最优化问题。在做题时，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。关键词：算法；动态规划；回溯法；目录一、问题描述11.1k乘积问题11.2最小重量机器问题1二、算法设计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 是相应的价格。试设计一个算法，给出总价格不超过 c 的最小重量机器设计。二、算法设计1.对于给定的I和k,计算I的最大k乘积。2.对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。三、设计原理3.1动态规划动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤： （1） 找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.2回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。四、问题分析与设计4.1k乘积问题1.分析最优解的结构为了方便起见，设I(s,t)是I的由s位开始的t位数字组成的十进制数，R(i,j)表示I(0,i)的j乘积。第j段的起始位置为第w位,1wj。则有如下关系R(i,j) = R(i,j-1)I(w,j-w)要使R(i,j)最大，则R(i,j-1)也是最大，所以最大乘积问题的最优解包含其子问题的最优解。2.建立递归关系设MaxIij表示I(0,i)的最大j乘积，则原问题的最优值为MaxInk。当k1时，MaxIn1 = I(0,n);当k1时，可利用最优子结构性质计算MaxInk,若计算MaxInk的第k段的起始位置为第w位，1wj，则有MaxInk = MaxIwk-1I(w,n-w)。由于在计算时并不知道第k段的起始位置w，所以w还未定。不过w的值只有n-k+2种可能，即k-1wn。所以MaxInk可以递归地定义为I(0,n)k1MaxInk =maxMaxIwk-1I(w,n-w)k1MaxInk给出了最优值，同时还确定了计算最优的断开位置w，也就时说，对于这个w有MaxInk = MaxIwk-1I(w,n-w)若将对应于MaxInk的断开位置w记为demarcationnk后，可递归地由demarcationnk构造相应的最优解。4.2最小重量机器设计问题1.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 若cpd，则为不可行解，剪去相应子树，返回到i-1层继续执行。 若cw=weight，则不是最优解，剪去相应子树，返回到i-1层继续执行。 若in，则算法搜索到一个叶结点，用weight对最优解进行记录，返回到i-1层继续执行； 用for循环对部件i从m个不同的供应商购得的情况进行选择(1jm）。 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十进制位所组成的十进制数long 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);printf(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 n, kwhile ( ( c=getchar() )!=#) /read integera+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 using namespace std;class Machine/机器类public:Machine(char *in, char *out);/构造函数Machine();/析构函数void Solve();/输出结果到文件protected:void Search(int i, int s, int l, int *e);/从第i个部件开始递归搜索void Print();/输出结果private:int n;/部件个数int m;/供应商个数int d;/价格上限int *w;/部件重量int *c;/部件价格int min;/最小重量int *plan;/选购的部件ofstream fout;/输出结果文件;#endif/*函数实现文件 最小重量机器设计问题.cpp*/#include 最小重量机器设计问题.hMachine:Machine(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 无法打开! n m d;/初始化部件个数n，供应商数m，价格限制dw = new int*n+1;for(int i = 1; i = n; i+)wi = new intm+1;for(int j = 1; j wij;/初始化部件重量c = new int*n+1;for(int i = 1; i = n; i+)ci = new intn+1;for(int j = 1; j cij;/初始化部件价格fin.close();min = INT_MAX;/初始化最小重量plan = new intn+1;for(int i = 1; i = n; i+)plani = 0;/初始化选购计划if( !fout )cerr 文件 out 无法打开! endl;exit(1);Machine:Machine()if(fout)fout.close();for(int i = 1; i = n; i+)if(wi)delete wi;if(ci)delete ci;if(w)delete w;if(c)delete c;void Machine:Solve()int *e;e = new intn+1;for(int i = 1; i = n; i+)ei = 0;Search(1, 0, 0, e);/第一个零件开始搜索，初始重量和价格是0Print();/输出函数void Machine:Search(int i, int s, int l, int *e)if(i = n+1)/选购完毕if(s min & l = d)/找到一个更优解min = s;/更新重量最小值for(int i = 1; i min)/重量超过min，剪枝 return;for(int j = 1; j = m; j+)ei = j;s += wij;/加上第i部件由j供应商提供的重量l += cij;/加上第i部件由j供应商提供的价格Search(i+1, s, l, e);/递归选购下一个部件s -= wij;l -= cij;void Machine:Print()fout min endl;for(int i = 1; i = n; i+)fout plani ;/*主函数文件 test.cpp*/#include 最小重量机器设计问题.hint main()char *in = input.txt;/输入文件char *out = output.txt;/输出文件Machine machine(in, out);/文件初始化机器machine.Solve();/回溯法求解return 0;六、结果分析1. 注释：输入一个三位数，将其分为两段，使这两端乘积最大。当这个三位数为521时，5与21相乘积最大，为1052. 总结算法