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