動(dòng)態(tài)規(guī)劃模擬題及答案

動(dòng)態(tài)規(guī)劃測(cè)試題一：填空題（每空2分，共20分）動(dòng)態(tài)規(guī)劃算法的步驟是（找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征）、（遞歸地定義最優(yōu)值）（以自底向上的方式計(jì)算最優(yōu)值）、（根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造最優(yōu)解）。為方便起見(jiàn)、將矩陣連乘積A.A.+1……A.簡(jiǎn)記為（A[i:j]）。動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是（最優(yōu)子結(jié)構(gòu)性質(zhì) ）和（重疊子問(wèn)題性質(zhì) ）。矩陣連乘問(wèn)題的算法可由（遞歸）設(shè)計(jì)實(shí)現(xiàn)。對(duì)于矩陣連乘問(wèn)題、設(shè)計(jì)算A[i:j]、1WiWjW口所需要的最少數(shù)乘次數(shù)為m[i][j]則原則問(wèn)題的最優(yōu)值為（m[1][n]）。動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干（ 子問(wèn)題）,先求解（ 子問(wèn)題）,然后從這些（ 子問(wèn)題）的解得到原問(wèn)題的解。二：綜合題（第一題5分其余各題15分，共50分）1.補(bǔ)充下面的最大子段和動(dòng)態(tài)規(guī)劃算法。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背包問(wèn)題：有5種物品，背包的容量為c=10,物品i的重量為訊其價(jià)值為vi:(w1,v1)=(2,6) (w2，v2)=(2,3) (w3,v3)=(6,5) (w4v4)=(5,4)(吟七)=(4,6),求最優(yōu)解及最優(yōu)值。解..?p[5+1]=((0,0)}又V(w5,w5)=(4,6)?.?q[5+1]=p[5+1](+(4,6)=((4,6)}則p[5]=m-其中的受控點(diǎn)=((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-其中的受控點(diǎn)={(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-其中的受控點(diǎn)={(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問(wèn)題的最優(yōu)值15.最優(yōu)解為p[1]={(0,0),(2,6),(4,9)(6,12),(8,15)}3.設(shè)n=4,計(jì)算其最優(yōu)值。(a1,a2,a3,a4)=(3,4,8.10),(b1,b2,b3,b4)3.設(shè)n=4,計(jì)算其最優(yōu)值。解:?.?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.???作業(yè)中的一種最優(yōu)調(diào)度方案為—3-4-2.4.設(shè)n=4,(\沔沔遇4)=(20,10,40,50),b(1A3,4)=(331,1),a(0,1，…4)=(2,3,1,1,1)，為了方便計(jì)算，每個(gè)已乘上16,試求此問(wèn)題的最優(yōu)二叉搜索樹(shù)。解：設(shè)sij記根結(jié)點(diǎn)的下標(biāo)mij=min{mik-1+mk+1j+wij}, iWji<k<j叫-1=0, XiWn.又???w曠如+4+虬+妃1+???+『」次+氣=w+b+aw=a-1毋滿(mǎn)歸出口.??可得下表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 ?'.得頭結(jié)點(diǎn)為板根據(jù)重復(fù)以上方法，可得最優(yōu)二叉搜索樹(shù)為:三：簡(jiǎn)答題（每題10分，共30分）1.寫(xiě)出設(shè)計(jì)流水作業(yè)調(diào)度問(wèn)題的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]*大子段和問(wè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;}對(duì)a[1..?n]進(jì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