动态规划模拟题及答案

动态规划测试题一：填空题（每空2分，共20分）动态规划算法的步骤是（找出最优解的性质，并刻画其结构特征）、（递归地定义最优值）（以自底向上的方式计算最优值）、（根据计算最优值时得到的信息构造最优解）。为方便起见、将矩阵连乘积A.A.+1……A.简记为（A[i:j]）。动态规划算法的两个基本要素是（最优子结构性质 ）和（重叠子问题性质 ）。矩阵连乘问题的算法可由（递归）设计实现。对于矩阵连乘问题、设计算A[i:j]、1WiWjW口所需要的最少数乘次数为m[i][j]则原则问题的最优值为（m[1][n]）。动态规划算法的基本思想是将待求解问题分解成若干（ 子问题）,先求解（ 子问题）,然后从这些（ 子问题）的解得到原问题的解。二：综合题（第一题5分其余各题15分，共50分）1.补充下面的最大子段和动态规划算法。intMaxSum(intn,int*a){intsum=0,b=0;for(inti=1;i<=n;i++){if(b>0){b+=a[i];besti=1;}elseb=a[i];if(b>sum){sum=b;bestj=i;}}returnsum;0—1背包问题：有5种物品，背包的容量为c=10,物品i的重量为讯其价值为vi:(w1,v1)=(2,6) (w2，v2)=(2,3) (w3,v3)=(6,5) (w4v4)=(5,4)(吟七)=(4,6),求最优解及最优值。解..・p[5+1]=((0,0)}又V(w5,w5)=(4,6)・.・q[5+1]=p[5+1](+(4,6)=((4,6)}则p[5]=m-其中的受控点=((0,0),(4,6)}5j 、又・.・(w4，v4)=(5,4)・.・q[5]®(w4，v4)={(0,0),(4,6)}©(5,4)={(5,4),(9,10)}・..w4.=p[5]Vq[5]={(0,0),(4,6),(5,4),(9,10)}又•.•(w3,v3)=(6,5)・•・q[4]=p[4]©(w3,v3)={(6,5),(10,11)}・・.m3.=p[4]Vq[4]={(0,0),(4,6),(6,5),(9,10),(10,11)}则p[3j=m3j-其中的受控点={(0,0),(4,6),(9,10),(10,11)}又V(w2,v2)=(2,3)・.・q[3]=p⑶©(w,v)={(2,3),(6,9)}2 2・・.m2.={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}p[2j]=m2-其中的受控点={(0,0),(2,3),(4,6),(6,9),(9,10)：j(10,11)}又(w1,v1)=(2,6)・•・q[2]=p[2]©柄,七)={(2,6),(4,9),(6,12),(8,15)}Am1={(0,0),92,3},(2,6),(4,6),(4,9),(6,9),(6,12),(8,15j),(9,10),(10,11)}・.・p[1]=(0,0),(2,6),(4,9),(6,12),(8,15)}.••此0—1问题的最优值15.最优解为p[1]={(0,0),(2,6),(4,9)(6,12),(8,15)}3.设n=4,计算其最优值。(a1,a2,a3,a4)=(3,4,8.10),(b1,b2,b3,b4)3.设n=4,计算其最优值。解:•.•min{a.,b.}Wmin{a.,b.}.*.min{a,b}Wmin{a,b}min{3；2}Wmin{4,6}1・•・首先加工i1,然后顼Vmin{a,b}Wmin{a,b}min{3,9}Wmin{8,6}・・・首先加工i1,然后加工i3.*.*min{a,b}Nmin{a,b}min{4：9}3N{8,2}32・・・首先加工i3,然后i2.*.*min{a,b}Wmin{a,b}min{3,15}Wmin{10,6}・・・首先加工七,然后加工i4.Vmin{a,b}Wmin{a,b}・・・首先加I工1i3,然后加ITi4.Vmin{a,b}Nmin{a,b}・・・首次加工1i4,然后加工i2.・・・作业中的一种最优调度方案为—3-4-2.4.设n=4,(\沔沔遇4)=(20,10,40,50),b(1A3,4)=(331,1),a(0,1，…4)=(2,3,1,1,1)，为了方便计算，每个已乘上16,试求此问题的最优二叉搜索树。解：设sij记根结点的下标mij=min{mik-1+mk+1j+wij}, iWji<k<j叫-1=0, XiWn.又•・•w旷如+4+虬+妃1+・・・+『」次+气=w+b+aw=a-1毋满归出口.・・可得下表w10=2W21=3W32=1Wn=1W54=1叫0=0叫1=0叫2=0m43=0m54=0wn=9W2=6W33=4Wu3叫1=9m.2=6叫3=3m44=3s11=1S22=2S33=3S44=4 W12=12W23=8Wt=5叫2=18m23=11叫4=8S12=1S23=2S34=3W13=14W24=10叫3=25m24=18S13=1 S24=2 w14=16m14=33s14=2 ・'.得头结点为板根据重复以上方法，可得最优二叉搜索树为:三：简答题（每题10分，共30分）1.写出设计流水作业调度问题的johnson算法。intFlowshop(intn,inta,intb,intc)classJobtype{public:intoperator<=(Jobtypea)const{return(k<=a.key);}intkey,index;booljob;}jobtype*d=newJobtype[n];for(inti=0;i<n;i++) {d[i].key=a[i]>b[i]?b[i]:a[i];d[i].job=a[i]<=b[i];d[i].index=i;sort(d,n);intj=0,k=n-1;for(inti=0;i<n;i++){if(d[i].job)c[j++]=d[i].index;elsec[k--]=d[i].index;j=a[c[0]];k=j+b[c[0]];for(inti=1;i<n;i++){

J+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}seleted;returnk;求序列a[1.・.n]*大子段和问题的分治算法。intuaxsubsum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{tltnttltntntKKKKK•ubtltnttltntntKKKKK•ubleftsum=uaxsubsum(ajeft,center);rightsum=uaxsubsum(a,center+1,right);s1=0;lefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1) s1=lefts;}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2) s2=rights;sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;returnsum;}对a[1..・n]进行一次快速划分的算法。template<classtype>intpartition(inta[],intl,inth){cin>>v;k=locate(a,1,n,v);if(k==0)return(false);else{x=a[1];a[1]=a[k];a[k]=x;return(partition1(a919n));intlocate(inta[],intl,inth,intv){i=l;while(i<=h