算法部分作業(yè)答案(編輯修改稿)
2025-08-22 09:46 本頁面
【文章內容簡介】 (收益) P=34+15=49 P=49+3=52 物品,都不能裝入.所以,貪心法求得的0/1背包問題的最優(yōu)解為x=(1,0,1,0,1,1,1)。即裝入第0,2,4,5,6物品 最大收益: P=52 但實際上，當y=(1,1,1,0,1,1,0) 即裝入第0,1,2,4,5物品,可獲收益為P=54,所以，貪心法求得的0/1背包問題的解x一定不是最優(yōu)解. 原因是: 對于0/1背包問題，貪心法并不能保證使其單位載重下的收益最大，因為通常在背包沒還裝滿時，卻再也裝不下任何物品，這樣，就使得單位載重下的物品收益減少,所以， 0/1背包問題通常不能用貪心法求解.63 設有帶時限的作業(yè)排序實例n=7，收益(p0, p1, p2, p3, p4, p5, p6)=(3,5,20,18,1,6,30)，作業(yè)的時限(d0, d1, d2, d3, d4, d5, d6)=(1,3,4,3,2,1,2),給出以此實例為輸入，執(zhí)行函數(shù)JS得到的用最優(yōu)解和最大收益。解:X={5,6,3,2} 最大收益為74函數(shù)JS如下:int JS(int *d, int *x, int n) { //設p0≥p1≥…≥pn1 int k=0。 x[0]=0。 for (int j=1。 jn。 j++){//O(n) int r=k。 while (r=0 amp。amp。 d[x[r]]d[j] amp。amp。 d[x[r]]r+1)r。 //搜索作業(yè)j的插入位置 if((r0 || d[x[r]]=d[j]) amp。amp。 d[j]r+1){ //若條件不滿足，選下一個作業(yè) for (int i=k。 i=r+1。 i) x[i+1]=x[i]。 //將x[r]以后的作業(yè)后移 x[r+1]=j。 k++。 //將作業(yè)j插入r+1處 } } return k。} 在執(zhí)行JS函數(shù)之前，必須先對輸入(即作業(yè))按作業(yè)的收益非增次序排序，結果為: 6,2,3,5,1,0,4X: 接著執(zhí)行JS函數(shù): 最初, 解集合X為空.6X:0 1 2 3 4 5 6 首先, 考慮作業(yè)6, 假設將其加入集合X, 即x[0]=6?？紤]X中的作業(yè)能否均如期完成,因為此時X中只有作業(yè)6,其截止時限為2,故,能如期完成,此時,將作業(yè)6加入作業(yè)子集X中,此時，子集X中的最大可用下標k=0。X:6 0 1 2 3 4 5 6 k 接著，考慮作業(yè)2. 首先搜索作業(yè)2在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時限的非減次序排序,因為d6=2,而d2=4,所以，可將作業(yè)2插在作業(yè)6的后面，即x[1]=2,得到X=(6,2),X:620 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因為d6=2=1, d2=4=2,所以，X中作業(yè)均能如期完成，將作業(yè)2加入子集X中. 子集X中的最大可用下標k=k+1=1X:620 1 2 3 4 5 6 k考慮作業(yè)3.首先搜索作業(yè)3在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時限的非減次序排序,因為d6=2, d2=4,而d3=3所以，可將作業(yè)3插在作業(yè)6的后面,作業(yè)2的前面，得到X=(6,3,2),X:6320 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因為d6=2=1, d3=3=2, d2=4=3所以，X中作業(yè)均能如期完成，將作業(yè)2加入子集X中. 子集X中的最大可用下標k=k+1=2X:6320 1 2 3 4 5 6 k考慮作業(yè)5.首先搜索作業(yè)5在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時限的非減次序排序,因為d6=2, d2=4, d3=3而d5=1所以，可將作業(yè)5插在作業(yè)6的前面,得到X=(5,6,3,2),X:56320 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因為d5=1=1,d6=2=2, d3=3=3, d2=4=4所以，X中作業(yè)均能如期完成，將作業(yè)5加入子集X中. 子集X中的最大可用下標k=k+1=3X:56320 1 2 3 4 5 6 k考慮作業(yè)1.首先搜索作業(yè)1在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時限的非減次序排序,因為d5=1,d6=2, d3=3,d2=4,而d1=3所以，可將作業(yè)1插在作業(yè)2的前面,作業(yè)3的后面,得到X=(5,6,3,1,2),X:563120 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因為d5=1=1,d6=2=2, d3=3=3, d1=34所以，X中1作業(yè)不能如期完成，所以，不能將作業(yè)1加入子集X. X:56320 1 2 3 4 5 6 k 接著考慮作業(yè)0,4均不能加入子集X,故，執(zhí)行JS得到的最優(yōu)解為X=(5,6,3,2),最大收益為P=p5+p6+p3+p2=30+20+18+6=74617,最佳裝載問題是將一批集裝箱裝上一艘載重為C的輪船，其中集裝箱i的重量為wi(0=i=n1),最優(yōu)裝載問題是指在裝載體積不受限制的情況下,求使得裝箱數(shù)目最多的裝載方案.(1)按貪心策略的要求,給出關于上述最優(yōu)化問題的形式化描述.(2)給出貪心法求解這一問題的最優(yōu)量度標準。(3)討論其最優(yōu)解的最優(yōu)子
電大資料相關推薦
鄂ICP備17016276號-1