《優(yōu)裝載問題》PPT課件

1、最優(yōu)裝載問題姓名：譚立威學(xué)號：0301307371精選ppt簡介問題描述實現(xiàn)原理貪心性質(zhì)代碼實現(xiàn)致謝2精選ppt問題描述有一批集裝箱要裝上一艘載重量為 c的輪船。第 i個集裝箱的重量為 Wi。 最優(yōu)裝載問題要求在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。3精選ppt問題描述問題可形式化描述為：設(shè)：xi表示第i個集裝箱是否裝載， xi = 0 or 1, i = 1 to n; 求：Max(x1+x2+xn)約束條件：W1*x1 + W2*x2 + + Wn*xn = c4精選ppt實現(xiàn)原理每次選擇時，從剩下的集裝箱中，選擇重量最小的集裝箱。通過這樣的選擇可以保證已經(jīng)選出來的集裝箱總

2、重量最小，裝載的集裝箱數(shù)量最多，直到船只不能再繼續(xù)裝載為止。5精選ppt證明考慮任意裝載容量為K的非空子問題Sk，令am是Sk中重量最小的集裝箱，則am在Sk的某個集裝箱裝載數(shù)量最多且總重量最少的最優(yōu)子集中。證明：令A(yù)k是Sk的一個最優(yōu)子集，且aj是Ak中重量最小的集裝箱。若aj=am，則證明am在Sk的某個最優(yōu)子集中。若ajam，則將Ak中的aj替換為am得到Ak，amweight (struct box*)b)-weight) return 1; else return 0;/按集裝箱重量對集裝箱進(jìn)行快速排序 qsort(boxes,8,sizeof(struct box),cmp);時間

3、復(fù)雜度為O(n2)11精選ppt代碼實現(xiàn)/累加重量 計算可裝載集裝箱數(shù)量maxLoad = 500;countLoad = 0;quantity = 0;for(i=0;i8;i+) /如果還能繼續(xù)裝載 if(boxesi.weight = maxLoad - countLoad) countLoad = countLoad + boxesi.weight; /計算最大裝載數(shù)量quantity quantity +; /獲取裝載標(biāo)記 flagboxesi.index = 1;時間復(fù)雜度O(n)12精選ppt代碼實現(xiàn)編號為6，2，5，7，3，0的集裝箱總重量為390單位且已被裝載，剩余的裝載容量

4、為10個單位，小于剩余任一集裝箱的重量。問題結(jié)束。在這個貪心解決算法中通過flag數(shù)組中的結(jié)果可以得到 x0,x1,x7=1,0,1,1,0,1,1,1，且xi = 6, i = 0 to 7總的時間復(fù)雜度為O(n2)+c*O(n)，即O(n2) (W0,W2,W7 = 100,200,50,90,150,50,20,80, 船只載重c=400)13精選ppt代碼實現(xiàn)截圖14精選ppt致謝感謝劉東林老師給予這次講課機會感謝邵舒迪同志的幫助Thanks for your attentions參考：算法導(dǎo)論第三版 十六章 定理16.1；互聯(lián)網(wǎng)：/p-422844096.html ；15精選ppt代

5、碼實現(xiàn)完整代碼#include #include / 集裝箱 結(jié)構(gòu)體 typedef struct box int weight;/重量 int index; /初始序號 ;/比較子函數(shù) int cmp (const void *a, const void *b) if(struct box*)a)-weight (struct box*)b)-weight) return 1; else return 0;int main() /初始化集裝箱集合 struct box boxes8 = 100,0,200,0,50,0,90,0,150,0,50,0,20,0,80,0 ; int flag

6、8 = 0;/集裝箱裝載標(biāo)志 int i ; int quantity; /可裝載集裝箱數(shù)量 int maxLoad; /船只最大載重 int countLoad;/已經(jīng)裝載重量 /輸出集裝箱初始數(shù)據(jù) printf(集裝箱初始數(shù)據(jù)); printf(n); for(i=0;i8;i+) printf(b%d:%d t,i,boxesi.weight); printf(n); /初始化 集裝箱序號 for(i=0;i8;i+) boxesi.index = i; printf(n); printf(快速排序之后：); printf(n); /按集裝箱重量對集裝箱進(jìn)行快速排序 qsort(boxe

7、s,8,sizeof(struct box),cmp); /從小到達(dá)輸出集裝箱重量 for(i=0;i8;i+) printf(b%d:%d t,i,boxesi.weight); printf(n); printf(n); printf(集裝箱初始時的下標(biāo) :); printf(n); /輸出集裝箱初始時的下標(biāo) for(i=0;i8;i+) printf(index%d:%d t,i,boxesi.index); printf(n); /累加重量 計算可裝載集裝箱數(shù)量 maxLoad = 500; countLoad = 0; quantity = 0; for(i=0;i8;i+) /如果還能繼續(xù)裝載 if(boxesi.weight = maxLoad - countLoad) countLoad = countLoad + boxesi.weight; /計算最大裝載數(shù)量quantity quantity +; /獲取裝載標(biāo)記 flagboxesi.index = 1; printf(n); printf(集裝箱最大裝載數(shù)：); printf(n); printf(quantity:%d,quantity); printf(n); printf(n);