下面程序段的所需要的計算時間為（）。intMaxSum(intn,int*a,int&besti,int&bestj)intMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0; for(inti=1;i<=n;i++){ intthissum=0; for(intj=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } returnsum;}有11個待安排的活動，它們具有下表所示的開始時間與結束時間，如果以貪心算法求解這些活動的最優安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（{1，4，8，11}）。141413121110987654f[i]122886535031S[i]1110987654321i所謂貪心選擇性質是指（所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到）。所謂最優子結構性質是指（問題的最優解包含了其子問題的最優解）。回溯法是指（具有限界函數的深度優先生成法）。6.用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為（O(h(n))）。7.回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排列樹）算法框架。8.用回溯法解0/1背包問題時，該問題的解空間結構為（子集樹）結構。9.用回溯法解批處理作業調度問題時，該問題的解空間結構為（排列樹）結構。10.用回溯法解0/1背包問題時，計算結點的上界的函數如下所示，請在空格中填入合適的內容：TypepKnap<Typew,Typep>::TypepKnap<Typew,Typep>::Bound(inti){//計算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//結點的上界//以物品單位重量價值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包if(i<=n)（b+=p[i]/w[i]*cleft）;returnb;}11.用回溯法解布線問題時，求最優解的主要程序段如下。如果布線區域劃分為的方格陣列，擴展每個結點需O(1)的時間，L為最短布線路徑的長度，則算法共耗時(O(mn))，構造相應的最短距離需要（O(L)）時間。for(inti=0;i<NumOfNbrs;i++){for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//該方格未標記grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布線Q.Add(nbr);}}12.用回溯法解圖的m著色問題時，使用下面的函數OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時（漸進時間上限）（O（mn））。BoolColor::OK(intk)BoolColor::OK(intk){//for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}13.旅行售貨員問題的解空間樹是（排列樹）。證明題1.一個分治法將規模為n的問題分成k個規模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：通過迭代法求得T（n）的顯式表達式為：試證明T（n）的顯式表達式的正確性。2.舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包，則此方法不一定能得到最優解（此題說明0/1背包問題與背包問題的不同）。證明：舉例如：p={7,4,4},w={3,2,2},c=4時，由于7/3最大，若按題目要求的方法，只能取第一個，收益是7。而此實例的最大的收益應該是8，取第2，3個。3.求證：O(f(n))+O(g(n))=O(max{f(n),g(n)})。證明：對于任意f1(n)O(f(n))，存在正常數c1和自然數n1，使得對所有nn1，有f1(n)c1f(n)。類似地，對于任意g1(n)O(g(n))，存在正常數c2和自然數n2，使得對所有nn2，有g1(n)c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的nn3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n))c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).4.求證最優裝載問題具有貪心選擇性質。（最優裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。設集裝箱已依其重量從小到大排序，(x1,x2,…,xn)是最優裝載問題的一個最優解。又設。如果給定的最優裝載問題有解，則有。）證明：解答題機器調度問題。問題描述：現在有n件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi，si<fi。[si，fi]為處理任務i的時間范圍。兩個任務i，j重疊指兩個任務的時間范圍區間有重疊，而并非指i，j的起點或終點重合。例如：區間[1，4]與區間[2，4]重疊，而與[4，7]不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優分配是指使用的機器最少的可行分配方案。問題實例：若任務占用的時間范圍是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，則按時完成所有任務最少需要幾臺機器？（提示：使用貪心算法）畫出工作在對應的機器上的分配情況。2.已知非齊次遞歸方程：，其中，b、c是常數，g(n)是n的某一個函數。則f(n)的非遞歸表達式為：。現有Hanoi塔問題的遞歸方程為：，求h(n)的非遞歸表達式。解：利用給出的關系式，此時有：b=2,c=1,g(n)=1,從n遞推到1，有：3.單源最短路徑的求解。問題的描述：給定帶權有向圖（如下圖所示）G=(V,E)，其中每條邊的權是非負實數。另外，還給定V中的一個頂點，稱為源。現在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。解法：現采用Dijkstra算法計算從源頂點1到其它頂點間最短路徑。請將此過程填入下表中。4432110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代4.請寫出用回溯法解裝載問題的函數。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：voidbacktrack(inti){//搜索第i層結點if(i>n)//到達葉結點更新最優解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c){//搜索左子樹x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;//搜索右子樹backtrack(i+1);}r+=w[i];}5.用分支限界法解裝載問題時，對算法進行了一些改進，下面的程序段給出了改進部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執行上有什么不同。////檢查左兒子結點Typewt=Ew+w[i];//左兒子結點的重量if(wt<=c){//可行結點if(wt>bestw)bestw=wt;//加入活結點隊列if(i<n)Q.Add(wt);}//檢查右兒子結點if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最優解Q.Delete(Ew);//取下一擴展結點解答：斜線標識的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設置為0，直到搜索到第一個葉結點時才更新bestw。因此在算法搜索到第一個葉子結點之前，總有bestw=0，r>0故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應提早更新bestw。又知算法最終找到的最優值是所求問題的子集樹中所有可行結點相應重量的最大值。而結點所相應得重量僅在搜索進入左子樹是增加，因此，可以在算法每一次進入左子樹時更新bestw的值。7.最長公共子序列問題：給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優子結構性質可建立遞歸關系如下：在程序中，b[i][j]記錄C[i][j]的值是由哪一個子問題的解得到的。請填寫程序中的空格，以使函數LCSLength完成計算最優值的功能。voidvoidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}函數LCS實現根據b的內容打印出Xi和Yj的最長公共子序列。請填寫程序中的空格，以使函數LCS完成構造最長公共子序列的功能（請將b[i][j]的取值與（1）中您填寫的取值對應，否則視為錯誤）。voidvoidLCS(inti，intj，char*x，int**b){if(i==0||j==0)retur