這個問題來自例1 - 2。船可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據這種思想可利用如下貪婪準則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。例1-7 假設n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用貪婪算法時，所考察貨箱的順序為7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。貨箱7 , 3 , 6 , 8 , 4 , 1的總重量為3 9 0個單位且已被裝載，剩下的裝載能力為1 0個單位，小于剩下的任何一個貨箱。在這種貪婪解決算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且?xi = 6。 定理1-1 利用貪婪算法能產生最佳裝載。 證實可以采用如下方式來證實貪婪算法的最優性：令x = [x1 , ..., xn ]為用貪婪算法獲得的解，令y =[ y1 , ..., yn ]為任意一個可行解，只需證實n ?i= 1xi ≥n ?i= 1yi 。不失一般性，可以假設貨箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分幾步將y 轉化為x，轉換過程中每一步都產生一個可行的新y，且n ?i = 1yi 大于等于未轉化前的值，最后便可證實n ?i = 1xi ≥n ?j = 1yi 。 根據貪婪算法的工作過程，可知在[0, n] 的范圍內有一個k，使得xi =1, i≤k且xi =0, i>k。尋找[ 1 ,n]范圍內最小的整數j，使得xj≠yj 。若沒有這樣的j 存在，則n ?i= 1xi =n ?i = 1yi 。假如有這樣的j 存在，則j≤k，否則y 就不是一個可行解，因為xj≠yj ，xj = 1且yj = 0。令yj = 1，若結果得到的y 不是可行解，則在[ j+ 1 ,n]范圍內必有一個l 使得yl = 1。令yl = 0，由于wj≤wl ，則得到的y 是可行的。而且，得到的新y 至少與原來的y 具有相同數目的1。 經過數次這種轉化，可將y 轉化為x。由于每次轉化產生的新y 至少與前一個y 具有相同數目的1，因此x 至少與初始的y 具有相同的數目1。貨箱裝載算法的C + +代碼實現見程序1 3 - 1。由于貪婪算法按貨箱重量遞增的順序裝載，程序1 3 - 1首先利用間接尋址排序函數I n d i r e c t S o r t對貨箱重量進行排序（見3 . 5節間接尋址的定義），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時間為O (nl o gn)（也可利用9 . 5 . 1節的堆排序及第2章的歸并排序），算法其余部分所需時間為O (n)，因此程序1 3 - 1的總的復雜性為O (nl o gn)。 程序13-1 貨箱裝船 template void ContainerLoading(int x[], T w[], T c, int n) {// 貨箱裝船問題的貪婪算法 // x[i] = 1 當且僅當貨箱i被裝載， 1<=i<=n // c是船的容量, w 是貨箱的重量 // 對重量按間接尋址方式排序 // t 是間接尋址表 int *t = new int [n+1]; I n d i r e c t S o r t ( w, t, n); // 此時, w[t[i]] <= w[t[i+1]], 1<=i < p>// 初始化x for (int i = 1; i <= n; i++) x[i] = 0; // 按重量次序選擇物品 for (i = 1; i <= n && w[t[i]] <= c; i++) { x[t[i]] = 1; c -= w[t[i]];} // 剩余容量 delete [] t; }
