最優(yōu)裝載問(wèn)題課件

簡(jiǎn)介問(wèn)題描述實(shí)現(xiàn)原理貪心性質(zhì)代碼實(shí)現(xiàn)致謝簡(jiǎn)介問(wèn)題描述1問(wèn)題描述有一批集裝箱要裝上一艘載重量為c的輪船。第i個(gè)集裝箱的重量為Wi。最優(yōu)裝載問(wèn)題要求在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

問(wèn)題描述有一批集裝箱要裝上一艘載重量為c的輪船。第i個(gè)集2問(wèn)題描述問(wèn)題可形式化描述為： 設(shè)：

xi表示第i個(gè)集裝箱是否裝載，xi=0or1,i=1ton;

求：

Max(x1+x2+…+xn)

約束條件：

W1*x1+W2*x2+…+Wn*xn<=c

問(wèn)題描述問(wèn)題可形式化描述為：3實(shí)現(xiàn)原理每次選擇時(shí)，從剩下的集裝箱中，選擇重量最小的集裝箱。通過(guò)這樣的選擇可以保證已經(jīng)選出來(lái)的集裝箱總重量最小，裝載的集裝箱數(shù)量最多，直到船只不能再繼續(xù)裝載為止。實(shí)現(xiàn)原理每次選擇時(shí)，從剩下的集裝箱中，選擇重量最小的集裝箱。4證明考慮任意裝載容量為K的非空子問(wèn)題Sk，令am是Sk中重量最小的集裝箱，則am在Sk的某個(gè)集裝箱裝載數(shù)量最多且總重量最少的最優(yōu)子集中。 證明：令A(yù)k是Sk的一個(gè)最優(yōu)子集，且aj是Ak中重量最小的集裝箱。若aj=am，則證明am在Sk的某個(gè)最優(yōu)子集中。若aj≠am，則將Ak中的aj替換為am得到Ak’，am<=aj。由于|Ak’|=|Ak|，所以Ak’也是Sk的一個(gè)集裝箱裝載數(shù)量最多的的最優(yōu)子集，且它包含am。證明考慮任意裝載容量為K的非空子問(wèn)題Sk，令am是Sk中重量5貪心性質(zhì)通過(guò)上述證明我們可以知道，每次比較計(jì)算得到最小的集裝箱，它在最優(yōu)解中，選出來(lái)之后，對(duì)余下的集裝箱（子問(wèn)題）采取同樣的策略選取最輕的集裝箱，放入最優(yōu)解當(dāng)中，得到局部最優(yōu)解，這樣逐步縮小問(wèn)題規(guī)模即縮小剩余載重量。最終得到全局最優(yōu)解。貪心性質(zhì)通過(guò)上述證明我們可以知道，每次比較計(jì)算得到最小的集裝6代碼實(shí)現(xiàn)系統(tǒng)環(huán)境：Win7操作系統(tǒng)開(kāi)發(fā)平臺(tái)：DEV-C++代碼實(shí)現(xiàn)系統(tǒng)環(huán)境：7代碼實(shí)現(xiàn)問(wèn)題實(shí)例假設(shè)集裝箱數(shù)量n=8,

八個(gè)集裝箱的重量是

[W0,W2,…,W7]=[100,200,50,90,150,50,20,80],

船只載重c=400。求該條件下的最優(yōu)裝載問(wèn)題。代碼實(shí)現(xiàn)問(wèn)題實(shí)例8代碼實(shí)現(xiàn)—數(shù)據(jù)結(jié)構(gòu)//集裝箱結(jié)構(gòu)體typedefstructbox{intweight;//重量

intindex;//初始序號(hào)};代碼實(shí)現(xiàn)—數(shù)據(jù)結(jié)構(gòu)9代碼實(shí)現(xiàn)//比較子函數(shù)intcmp(constvoid*a,constvoid*b){if(((structbox*)a)->weight>((structbox*)b)->weight)return1;elsereturn0;}//按集裝箱重量對(duì)集裝箱進(jìn)行快速排序qsort(boxes,8,sizeof(structbox),cmp);時(shí)間復(fù)雜度為O(n2)代碼實(shí)現(xiàn)//比較子函數(shù)10代碼實(shí)現(xiàn)//累加重量計(jì)算可裝載集裝箱數(shù)量maxLoad=500;countLoad=0;quantity=0;for(i=0;i<8;i++){//如果還能繼續(xù)裝載if(boxes[i].weight<=maxLoad-countLoad){countLoad=countLoad+boxes[i].weight;//計(jì)算最大裝載數(shù)量quantityquantity++;//獲取裝載標(biāo)記flag[boxes[i].index]=1;}}時(shí)間復(fù)雜度O(n)代碼實(shí)現(xiàn)//累加重量計(jì)算可裝載集裝箱數(shù)量11代碼實(shí)現(xiàn)編號(hào)為6，2，5，7，3，0的集裝箱總重量為390單位且已被裝載，剩余的裝載容量為10個(gè)單位，小于剩余任一集裝箱的重量。問(wèn)題結(jié)束。在這個(gè)貪心解決算法中通過(guò)flag數(shù)組中的結(jié)果可以得到

[x0,x1,…,x7]=[1,0,1,1,0,1,1,1]，且∑xi=6,i=0to7總的時(shí)間復(fù)雜度為O(n2)+c*O(n)，即O(n2)

([W0,W2,…,W7]=[100,200,50,90,150,50,20,80],船只載重c=400)代碼實(shí)現(xiàn)編號(hào)為6，2，5，7，3，0的集裝箱總重量為390單12代碼實(shí)現(xiàn)—截圖代碼實(shí)現(xiàn)—截圖13致謝感謝劉東林老師