《动态规划模拟题及答案》由会员分享，可在线阅读，更多相关《动态规划模拟题及答案（7页珍藏版）》请在金锄头文库上搜索。
1、动态规划测试题一：填空题（每空2分，共20分）1动态规划算法的步骤是（找出最优解的性质，并刻画其结构特征）、（递 归地定义最优值）（以自底向上的方式计算最优值）、（根据计算最优值 时得到的信息构造最优解 ）。2为方便起见、将矩阵连乘积AiAi+1坷简记为（Ai:j）。3. 动态规划算法的两个基本要素是（最优子结构性质）和（ 重叠子问题性质）4. 矩阵连乘问题的算法可由（ 递归 ）设计实现。5对于矩阵连乘问题、设计算Ai:j、1 WiWjWn所需要的最少数乘次数为 mij则原则问题的最优值为（m1n）。6.动态规划算法的基本思想是将待求解问题分解成若干（ 子问题 ）, 先求解（ 子问题 ）,然后
2、从这些（ 子问题 ）的解得到原问题的解。二 综合题（第一题5分其余各题15分，共50分）1补充下面的最大子段和动态规划算法。int MaxSum(int njnt *a) int sum=0,b=0;for(int i=1;i0)b+=ai; besti=1; else b=ai;if(bsum) sum=b; bestj=i;return sum;2. 01背包问题：有5种物品，背包的容量为c=10,物品i的重量为wi其价 值为vi:(w1,v1)=(2,6)(w2，v2)=(2j3)(w3,v3)=(6,5)(w4、v4)=(5,4)(W5，v5)=(4,6),求最优解及最优值。解5+1=
3、 (0, 0)又 V(w,w ) = (4, 6)55q5+1=p5+1(4, 6) = (4, 6)则p5=m -其中的受控点=(0, 0), (4, 6)5j又(w,v ) =(5,4)44q5 (w,v) = (0,0),(4,6)(5,4) = (5,4),(9,10)44w4=p5 Vq5 = (0,0),(4,6),(5,4),(9,10) 又v(w,v ) =(6,5)33q4=p4(w3,v3) = (6,5),(10,11)m,=p4yq4 = (0,0),(4,6),(6,5),(9,10),(10,11) 则 p3=m3其中的受控点=(0,0),(4,6),(9,10),
4、(10,11) 又(w,v )二3)2 2 q 3=p 3 (w,v) = (2, 3),(6,9)2 2m2 = (0,0),(2,3),(4,6), (6,9),(9,10),(10,11) p2=m2-其中的受控点=(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)又(W,V) = (2,6)q2=p2(w,v) = (2,6),(4,9),(6,12),(8,15)2 2Am1=(0,0),92,3,(2,6),(4,6),(4,9),(6,9),(6,12),(8,15 1J ),(9,10),(10,11)p1= (0, 0), (2, 6), (4, 9
5、), (6, 12), (8, 15)此0 1问题的最优值15.最优解为 p1 = (0,0),(2,6),(4,9)(6, 12), (8, 15)3. 设 n=4, (a1,a2,a3,a4)=(3,4,810),0243小4)=(6,2,9,15)5求作业中的一种最 优调度方案并计算其最优值。)解：mina,bWmina,bi jj i.*.mina ,b Wmina ,b 1 、2 . 2、 1min3,2 Wmin4,6首先加工i,然后i。1 2Vmina ,b Wmina ,b 1 331min3,9 Wmin8,6 首先加工i,然后加工i3. *.*mina ,b Mmina ,
6、b 2 332min4,9 M8,2 首先加工i,然后i.32*.*mina ,b Wmina ,b min3,15 Wmin10,6首先加工i,然后加工i.14Vmina ,b Wmina ,b 3443首先加工i,然后加工i4Vmina ,b Mmina ,b 首次加工1 i ,然后加工i42作业中的一种最优调度方案为1-3-4-2.4. 设 n=4,(斗込円込4)=(2，1，40,50),b(1234)=(39,1,1),a(O,14)=(231, 1,1),为 了方便计算，每个气山已乘上16,试求此问题的最优二叉搜索树。解：设sij记根结点的下标Wn.min m.k 1+mk+1.+w
7、.,ik-1 k+1j iji k j叫-1=,又 wij=ai_1+bi+a.+bi+1+w+b +aw =r为满归出口 可得下1表=w +b +aw10=2W21=3W32=1W43=1W54=1叫0=0m21=0叫2=0m43=0叫4=0Wii=9W2=6W33=4%3m1i=9m.2=6叫3=3m.=3sii=1S22=2S33=3s44=4W12=12W23=8W4=5m12=18m23=11叫4=8S12=1S23=2S34=3W13=14W24=10m13=25m=18S13=1S24=2W14=16ml4=33s14=2:得头结点为根据重复以上方法，可得最优二叉搜索树为:三：简
8、答题(每题10分，共30分)1写出设计流水作业调度问题的johnson算法。int Flowshop(int n,int a,int bjnt c)class Jobtype public:int operatorbi? bi:ai; di.job=aiv=bi; di.index=i;sort(d,n);int j=0,k=n-1; for(int i=0;ivn;i+) if(di.job) cj+=di.index; else ck-=di.index;j=ac0; k=j+bc0;for(int i=1;ivn;i+) J+=aci; k=jvk?k+bci:j+bci; selete
9、 d; return k;2求序列a1n最大子段和问题的分治算法。int uaxsubsum(int *a,int left,int right) sum=aleft0? aleft:0;intintintint intint sum=0; if(left=right) elsecenter=(left+right)/2; leftsum=uaxsubsum(a,left9center); rightsum=uaxsubsum(a,center+1,right); s1=0;lefts=0;for(int i=center;i=left;i-) lefts+=ai;if(leftss1)s1=
10、lefts;int s2=0;int rights=0;for(int i=center+1;iv=right;i+) rights+=ai;if(rightss2)s2=rights;sum=s1+s2;if(sumvleftsum) sum=leftsum; if(sumvrightsum) sum=rightsum; return sum;3对a1n进行一次快速划分的算法。templatevclass type int partition(int a,int l,int h) cinv; k=locate(a,1,n,v);if(k=0) return(false); else x=a1;a1=ak;ak=x;return(partition1(a4,n);int locate(int a,int ljnt h,int v) i=l;while(ih) return(O);else return(i);int partition1(int a,int l,int h) i=lj=h;x=ai;while(ij)while(i=x) j-; ai=aj;while(ij&ai=x) i+; aj=ai; ai=x;
