箱子裝箱問題

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ū)別在于各物品首先按容量遞減的次序排列，即對于l in，有sisi+1。 (4) 最優(yōu)匹配遞減法（ Best Fit Decreasing, BFD） 此法與BF相似，區(qū)別在于各物品首先按容量遞減的次序排列，即對于l in，有sisi+1。競賽樹是一類完全二叉樹，分為贏者樹和輸者樹。贏者樹就是在每一個(gè)內(nèi)部節(jié)點(diǎn)中記錄比賽贏的一方，輸者樹就是記錄輸?shù)囊环健８傎悩涞耐獠抗?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