箱子裝箱問題_第1頁
箱子裝箱問題_第2頁
箱子裝箱問題_第3頁
箱子裝箱問題_第4頁
箱子裝箱問題_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、6班 李康 201400301237問題描述: 在箱子裝載問題中,有若干個(gè)容量為c的箱子和n個(gè)待裝載入箱子中的物品。物品i需占si個(gè)單元(0sic)。所謂成功裝載(feasiblepacking),是指能把所有物品都裝入箱子而不溢出,而最優(yōu)裝載(optimalpacking)則是指使用了最少箱子的成功裝載。(1) 最先匹配法(First Fit, FF) 物品按1,2,n的順序裝入箱子。假設(shè)箱子從左至右排列。每一物品i 放入可盛載它的最左箱子。 (2) 最優(yōu)匹配法(Best Fit, BF) 設(shè)cAvailj為箱子j的可用容量。初始時(shí),所有箱子的可負(fù)載容量為c。 物品i放入具有最小cAvail

2、且容量大于si的的箱子中。 (3) 最先匹配遞減法(First Fit Decreasing, FFD) 此方法與FF類似,區(qū)別在于各物品首先按容量遞減的次序排列,即對(duì)于l in,有sisi+1。 (4) 最優(yōu)匹配遞減法( Best Fit Decreasing, BFD) 此法與BF相似,區(qū)別在于各物品首先按容量遞減的次序排列,即對(duì)于l in,有sisi+1。競(jìng)賽樹是一類完全二叉樹,分為贏者樹和輸者樹。贏者樹就是在每一個(gè)內(nèi)部節(jié)點(diǎn)中記錄比賽贏的一方,輸者樹就是記錄輸?shù)囊环健8?jìng)賽樹的外部節(jié)點(diǎn)就是所有參加比賽的選手,其上一層為第一輪比賽贏或輸?shù)倪x手class WinnerTreepublic:Wi

3、nnerTree(int TreeSize = 10);WinnerTree() delete t; void Initialize(T a, int size, int(*winner)(T a, int b, int c);/初始化int Winner()const return(n) ? t1 : 0; int Winner(int i)const return(i n) ? ti : 0; void RePlay(int i, int(*winner)(T a, int b, int c);/成員改變時(shí) void FirstFitPack(int s, int n, int c);/最

4、先匹配算法private:int MaxSize;int n;/當(dāng)前大小int LowExt;/最底層的外部節(jié)點(diǎn)int offset;/2k-1int *t;T *e;/元素?cái)?shù)組void WinnerTree:FirstFitPack(int s, int n, int c)/箱子容量c,物品數(shù)量n,s【】為各物品所需要的空間int(*winner)(T a, int b, int c);WinnerTree*W = new WinnerTree(n);int *avail = new intn + 1;/初始化n個(gè)箱子和贏者樹for (int i = 1; i Initialize(avai

5、l, n, winner);/將物品放入箱子中for (int i = 1; i = n; i+)int p = 2; while (p Winner(p);if (availwinp si)p+;p *= 2;int b;p /= 2;if (p Winner(p);if (b 1 & availb - 1 = si) b-;else b = W-Winner(p / 2);cout Pack object i in bin b RePlay(b, winner);AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一,所以它也被稱為高度平衡樹。查找、插入和刪

6、除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個(gè)樹。高度為 h 的 AVL 樹,節(jié)點(diǎn)數(shù) N 最多2h 1; 最少N(h)=N(h 1) +N(h 2) + 1。class avl_treepublic: void BestFitPack(int s, int n, int c);avl_tree() head = NULL; bool FindGE(const T &k, T &Kout)const;bool insert(node* &q, T &e);/插入節(jié)點(diǎn)bool remove(node* &q, T e);/刪除節(jié)點(diǎn)void print

7、(node* &q, int level);/格式化打印樹void middle_visit(node* &q);/中序遍歷node*& get_head() return head; /返回根節(jié)點(diǎn)的引用,注意是引用bool avl_tree:FindGE(const T &k, T &Kout)const/尋找值=k的最小元素node *p = head, *s = 0;/指向迄今所找到的=k的最小元素while (p)if (k elem)s = p;p = p-left;else p = p-right;if (!s)return false;Kout = s-elem; return true;void avl_tree:BestFitPack(int s, int n, int c)/n物品個(gè)數(shù),c箱子容量,s物品的大小int b = 0;avl_tree A;for (int i = 0; i = n; i+)int k;node P;if (A.FindGE(si, k)A.remove(A.get_head(), k);k -= si;if (k!= 0) A.insert(A.get_head(), k

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論