算法作業(yè)解答

第六章 動態(tài)規(guī)劃法 P137 2,3,42.解答:cost[i]表示從頂點i到終點n-1的最短路徑，path[i]表示從頂點i到終點n-1的路徑上頂點i的下一個頂點。cost[i]=min{cij+cost[j]} path[i]=?cij+cost[j]最小的ji0123456789101112131415Cost[i]1813161310912768759430Path[i]145778911111113141415150得到最短路徑0->1->4->7->11->14->15，長度為183有5個物品，其重量分別是｛3,2,1,4,5｝，價值分別為｛25,20,15,40,50｝，背包的容量為6。V[i][j]表示把前i個物品裝入容量為j的背包中獲得的最大價值。0 1 2 3 4 5 60W1=3,V1=251W2=2 V2=200W1=3,V1=251W2=2 V2=202W3=1,V3=153W4=4,V4=40W5=5V5=5045最優(yōu)解為(0，0，1，0，1)最優(yōu)值為65.0十0000000100252525.25.00f2025254545015i203540456001520354055600152035405565X=1X=1x=0x=0x=14.序列A=(x,z,y,z,z,，序，B=(z,x,y,y,z,x,z)，建立兩個(m+1)X(n+1)的二維表L和表S，分別存放搜索過程中得到的子序列的長度和狀態(tài)。z,x,y,y,z,x,z)0123456701234567000000000000000001x001111111021222122z011112222012221213y011222223032112224z011223334012321215z011223345012321216y011233346032112237x01223344703123212(a)長度矩陣L最長公共子序列長度為4,序列為(z,y,y,x)(b)狀態(tài)矩陣S第七章貪心算法2.背包問題：有7個物品，背包容量W=15。將給定物品按單位重量價值從大到小排序，結果如下:物品重量伽）價值仞價值/重量（襯*）序號（從大到?。?210522355/36351534477175166164184.5371335設背包容量為^共有n個物品，物品重量存放在數組w[n]中，價值存放在數組v[n]中，問題的解存放在數組x[n]中。按算法7.6 背包問題1.改變數組w和v的排列順序，使其按單位重量價值v[i]/w[i]降序排列；將數組x[n]初始化為0； //初始化解向量i=1;循環(huán)直到（w[i]>C）x[i]=1; //將第i個物品放入背包C=C-w[i];i++;x[i]=C/w[i];得出，該背包問題的求解過程為:：x[1]=1;c=15-1=14v=6x[2]=1;c=14-2=12V=6+10=10x[3]=1;c=12-4=8V=16+18=34x[4]=1;c=8-5=3V=34+15=49x[5]=1;c=3-1=2V=49+3=52x[6]=2/3;c=0;V=52+5*2/3=156/3最優(yōu)值為156/3最優(yōu)解為（1,1,1,1,1,2/3,0））（x[i]按排序后物品的順序構造）5.可以將該問題抽象為圖的著色問題，活動抽象為頂點，不相容的活動用邊相連（也可以將該問題理解為最大相容子集問題,重復查找剩余活動的最大相容子集，子集個數為所求）.具體參見算法7.3

算法7.3——圖著色問題color[1]=1;//頂點1著顏色1for(i=2;i<=n;i++)〃其他所有頂點置未著色狀態(tài)color[i]=0;k=0;循環(huán)直到所有頂點均著色k++;//取下一個顏色for(i=2;i<=n;i++) 〃用顏色k為盡量多的頂點著色4.2.1若頂點i已著色，則轉步驟4.2，考慮下一個頂點；4.2.2若圖中與頂點i鄰接的頂點著色與頂點i著顏色k不沖突，則color[i]=k;輸出k;第八章回溯法搜索空間(a)一個無向圖(b)回溯法搜索空間(a)一個無向圖(b)回溯法搜索空間最優(yōu)解為(1,2,1,2,3)TOC\o"1-5"\h\z5.0-1背包問題 寸/乙WX<c?可行性約束函數：.，?，? 1?上界函數：:r=YVii=k+1 1搜索空間6.該問題抽象為01背包問題，正整數為物品重量，Y為背包容量，具體代碼參考01背包算法。第九章分支限界法解：應用貪心法求得近似解：（1,4,2,3），其路徑代價為：3+5+7+6=21，這可以作為該問題的上界。把每一個任務的最小代價相加，可以得到下界3+5+3+6=17。所以，目標函數的界為［17,21］。lb限界函數為：lb第k行的最小值搜索空間如下:

（X表示該結點被丟棄，結點上方的數字表示搜索順序）6：最優(yōu)解為（110101）,最優(yōu)值為53,搜索空間樹略解答：物品重量（核）價值（羽）價值/重量（襯*）12157.52412332634388/3551111/5610181.8應用貪心法求得近似解：（1,1,1,1,1,0），最優(yōu)值為52,這可以作為該問題的下界。限界函數為：Lb=v+（W-w）*Vi+1/Wi+1所以，目標函數的界為［52,150］。。搜索空間如下：

結點上方的數字表示搜索順序，結點上方的數字表示搜索順序，*表示刪除該節(jié)點（44結點后的擴展結點略，最優(yōu)值為53，藍色標示）((1)(2)7：最優(yōu)解為（4312），最優(yōu)值為40,sum1[k+1]=sum1[k]+tk+1,1sum2[k+1]=max{sum1[k+1],su