箱子装箱问题

1、6班 李康 201400301237问题描述： 在箱子装载问题中，有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占si个单元（0sic）。所谓成功装载（feasiblepacking），是指能把所有物品都装入箱子而不溢出，而最优装载（optimalpacking）则是指使用了最少箱子的成功装载。（1) 最先匹配法（First Fit, FF） 物品按1，2，n的顺序装入箱子。假设箱子从左至右排列。每一物品i 放入可盛载它的最左箱子。 (2) 最优匹配法（Best Fit, BF） 设cAvailj为箱子j的可用容量。初始时，所有箱子的可负载容量为c。 物品i放入具有最小cAvail

2、且容量大于si的的箱子中。 (3) 最先匹配递减法（First Fit Decreasing, FFD） 此方法与FF类似，区别在于各物品首先按容量递减的次序排列，即对于l in，有sisi+1。 (4) 最优匹配递减法（ Best Fit Decreasing, BFD） 此法与BF相似，区别在于各物品首先按容量递减的次序排列，即对于l in，有sisi+1。竞赛树是一类完全二叉树，分为赢者树和输者树。赢者树就是在每一个内部节点中记录比赛赢的一方，输者树就是记录输的一方。竞赛树的外部节点就是所有参加比赛的选手，其上一层为第一轮比赛赢或输的选手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);/成员改变时 void FirstFitPack(int s, int n, int c);/最

4、先匹配算法private:int MaxSize;int n;/当前大小int LowExt;/最底层的外部节点int offset;/2k-1int *t;T *e;/元素数组void WinnerTree:FirstFitPack(int s, int n, int c)/箱子容量c，物品数量n，s【】为各物品所需要的空间int(*winner)(T a, int b, int c);WinnerTree*W = new WinnerTree(n);int *avail = new intn + 1;/初始化n个箱子和赢者树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树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、

6、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。高度为 h 的 AVL 树，节点数 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);/插入节点bool remove(node* &

7、;q, T e);/删除节点void print(node* &q, int level);/格式化打印树void middle_visit(node* &q);/中序遍历node*& get_head() return head; /返回根节点的引用，注意是引用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物品个数，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()