基于貪心法的裝箱問題---search-readpudncom

1、基于貪心法的裝箱問題【問題】裝箱問題問題描述：有一個箱子容量為V(正整數(shù)，0V20000），同時有n個物品（0n30),每個物品有一個體積（正整數(shù)）。要求從n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。 【算法設計的思想】貪心法是求解關于獨立系統(tǒng)組合優(yōu)化問題的一種簡單算法，求最小生成樹的Kruskal算法就是一種貪心算法。貪心法的基本思路是：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。 該算法存在問題： 1. 不能保證求得的最后解是最佳的； 2. 不能用來求最大或最小解問題； 3. 只能求滿足某些約束條件的

2、可行解的范圍。貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。 例如平時購物找錢時，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因為銀行對其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為

3、15單位的硬幣。按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優(yōu)的解應是3個5單位面值的硬幣。若考察將n種物品的集合分劃成n個或小于n個物品的所有子集，最優(yōu)解就可以找到。但所有可能劃分的總數(shù)太大。對適當大的n，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝箱問題采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個能放進去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。不失一般性，設n件物品的體積是按從大到小排好序的，即有v0v1vn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然后按排序結果對物品重新編號

4、即可?！舅惴ǖ牧鞒虉D】輸入箱子的容積輸入物品總數(shù)N輸入各物品體積預置已用箱子鏈為空預置已用箱子計數(shù)器box_count為0開始i=0;in;i+。從已用的第一只箱子開始順序尋找能放入物品i 的箱子j已用箱子能不能再放物品i已用箱子都不能再放物品i，另用一個箱子j，并將物品i放入該箱子，box_count+否則，將物品i放入箱子j【算法設計的思想】裝箱算法簡單描述如下： 輸入箱子的容積； 輸入物品種數(shù)n； 按體積從大到小順序，輸入各物品的體積； 預置已用箱子鏈為空； 預置已用箱子計數(shù)器box_count為0； for (i=0;in;i+) 從已用的第一只箱子開始順序尋找能放入物品i 的箱子j；

5、 if （已用箱子都不能再放物品i） 另用一個箱子j，并將物品i放入該箱子； box_count+； else 將物品i放入箱子j； 上述算法能求出需要的箱子數(shù)box_count，并能求出各箱子所裝物品。 若每只箱子所裝物品用鏈表來表示，鏈表首結點指針存于一個結構中，結構記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上算法編寫的程序?！境绦颉?include#includeusing namespace std;int v,n;int volume31;/存儲n件物品的體積 int h20001;/hi=1,表示n件物品通過某種組合，所構成的體積和正和

6、等于i; /hi=0,表示n件物品無論如何組合，體積和都無法等于i int main() freopen(in.txt,r,stdin); freopen(out.txt,w,stdout); int v,n,i,j,k; while(cinvn) for(i=1;ivolumei; memset(h,0,sizeof(h); h0=1; for(i=1;i=volumei;k-) hk=hk|hk-volumei; j=v; while(j0&hj=0) j-; coutv-jendl; return 0; 【運行結果分析】輸入 24 一個整數(shù)，表示箱子容量 6 一個整數(shù)，表示有n個物品接下

7、來n行，分別表示這n個物品的各自體積。 129 8 7 7 3輸出：0 一個整數(shù)，表示箱子剩余空間 【算法設計分析】本題是經典問題：0-1背包的特殊例子（加強了已知條件）。用整形數(shù)組volume存儲各件物品的體積，用布爾型函數(shù)h(i,k)表示前i個物品通過組合能否恰好裝滿容量k的空間，則考慮第i件物品，如果沒有被選中，則問題轉化為h(i-1,k);如果第i件物品被選中了，則問題轉化為h(i-1,k-volumei),因此有如下的表達式：h(i,k)=h(i-1,k-volumei) | h(i-1,k); k從V開始遞減，判斷h(n,k)是否為真，第一個符號要求的k即為剩余空間最小時消耗的體積

8、。 如果此時直接編寫程序，就要定義一個二維數(shù)組，空間復雜度時n*v,注意到了n,v的取值范圍很大，所以用二維數(shù)組存儲就會有問題。 我們注意到，h(i,k)的取值僅與h(i-1,0)h(i-1,k)有關，且如果h(i-1,k)=true,必然有h(i,k)=true,h(i,k)的值存在繼承性，而程序結束時，我們也只關心h(n,k),因此，我們可以用一維數(shù)組h(k)來存儲中間信息。為了避免重復計算，可以讓k從大到小變化，為了避免出現(xiàn)負數(shù)，k的變化范圍為vvolumei.【收獲體會】這個實驗讓我深刻理解了貪心法，貪心法顧名思義就是說要貪,要一點一點的貪,歇斯底里地貪,嚼字一點的講,就是說求一個問題的最優(yōu)解時,將這個問題肢解為一系列的局部性的問題,然后通過在每個局部得到最優(yōu)以使得在全局得到最優(yōu).其實這點挺有意思的,整