binType.h
// 用于首次装配包装的类别 #ifndef BINTYPE_H #define BINTYPE_H struct binType { int unusedCapacity; // 未使用容量 bool operator <= (binType& right) const {return (unusedCapacity >= right.unusedCapacity) ? true : false;} }; #endif
firsFitPack.h
#ifndef FIRSTFITPACK_H #define FIRSTFITPACK_H #include <iostream> #include "binType.h" #include "completeWinnerTree.h" // 货物数组 货物数量 每个箱子的容量 void firsFitPack(int *objectSize, int numberOfObjects, int binCapacity) {// 输出箱子容量为 binCapacity 的最先适配装载 // objectSize[1:numberOfObjects] 是物品大小 int n = numberOfObjects; // 物品数量 // 初始化 n 个箱子和赢者树 binType *bin = new binType [n + 1]; // 箱子 for (int i = 1; i <= n; i++) bin[i].unusedCapacity = binCapacity; completeWinnerTree<binType> winTree(bin, n); // 将物品装到箱子里 for (int i = 1; i <= n; i++) {// 把物品 i 装入一个箱子 // 找到第一个足够容量的箱子 int child = 2; // 从根的左孩子开始搜索 while (child < n) { int winner = winTree.winner(child); if (bin[winner].unusedCapacity < objectSize[i]) child++; // 第一个箱子的右子树 child *= 2; // 移到左孩子 } int binToUse; // 设置为要使用的箱子 child /= 2; // 撤销向最左孩子的移动 if (child < n) {// 在一个树节点 binToUse = winTree.winner(child); // 若 binToUse 是右孩子,则要检查箱子 binToUse - 1 // 即使 binToUse 是左孩子,检查箱子 binToUse - 1 也不会有问题 if (binToUse > 1 && bin[binToUse - 1].unusedCapacity >= objectSize[i]) binToUse--; } else // 当 n 是奇数 binToUse = winTree.winner(child / 2); std::cout << "包裹 object " << i << " 在 bin " << binToUse << std::endl; bin[binToUse].unusedCapacity -= objectSize[i]; winTree.rePlay(binToUse); } } #endif // !FIRSTFITPACK_H
completeWinnerTree.h
#ifndef COMPLELEWINNERTREE_H #define COMPLELEWINNERTREE_H #include "winnerTree.h" #include "myExceptions.h" template<typename T> class completeWinnerTree : public winnerTree<T> { public: completeWinnerTree(T *thePlayer, int theNumberOfPlayers) { tree = nullptr; initialize(thePlayer, theNumberOfPlayers); } ~completeWinnerTree() {delete [] tree;} void initialize(T*, int) override; int winner() const override {return tree[1];} // 返回赢者树的索引 int winner(int i) const {return (i < numberOfPlayers) ? tree[i] : 0;} // 在节点i返回比赛的获胜者 void rePlay(int) override; // 在参赛者 thePlater 的分数变化后重赛 void output() const; private: int lowExt; // 最底层外部节点个数 int offset; // offset = 2^log(n - 1) - 1 n : 外部节点个数 s : 最底层最左端内部节点编号 int *tree; // 赢者树数组 int numberOfPlayers; T *player; // 参赛者(外部节点) void play(int, int, int); }; template<typename T> void completeWinnerTree<T>::initialize(T *thePlayer, int theNumberOfPlaters) {// 为玩家创建赢者树 [1:NumberOfPlayer] int n = theNumberOfPlaters; if (n < 2) throw illegalParameterValue("必须至少有2名球员"); player = thePlayer; numberOfPlayers = n; delete [] tree; tree = new int [n]; // 计算 s = 2^log(n-1) int i, s; for (s = 1; 2 * s <= n; s += s); lowExt = 2 * (n - s); offset = 2 * s - 1; // 进行最低级别外部节点的匹配 for (i = 2; i <= lowExt; i += 2) play((offset + i) / 2, i - 1, i); // 处理剩余的外部节点 if (n % 2 == 1) {// 奇数 n,play 特殊的内部节点和外部节点 play(n / 2, tree[n - 1], lowExt + 1); i = lowExt + 3; } else i = lowExt + 2; // i 是剩余最左侧的外部节点 for (; i <= n; i += 2) play((i - lowExt + n - 1) / 2, i - 1, i); } template<typename T> void completeWinnerTree<T>::play(int p, int leftChild, int rightChild) {// 从树开始进行比赛 [p] // leftChild 是 p 的左子树 // rightChild 是 p 的右子树 tree[p] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild; // 如果在正确的子级,可能会有更多匹配 while (p % 2 == 1 && p > 1) {// 正确的孩子 tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ? tree[p - 1] : tree[p]; p /= 2; // 去找家长 } } template<typename T> void completeWinnerTree<T>::rePlay(int thePlayer) {// 在参赛者 thePlayer 的分数变化后重赛 int n = numberOfPlayers; if (thePlayer <= 0 || thePlayer > n) throw illegalParameterValue("玩家索引是非法的"); int matchNode, // 要进行下一场比赛的节点 leftChild, // 匹配节点的左子节点 rightChild; // 匹配节点的右子节点 // 查找第一个匹配节点及其子节点 if (thePlayer <= lowExt) {// 从最底层开始 matchNode = (offset + thePlayer) / 2; leftChild = 2 * matchNode - offset; rightChild = leftChild + 1; } else { matchNode = (thePlayer - lowExt + n - 1) / 2; if (2 * matchNode == n - 1) { leftChild = tree[2 * matchNode]; rightChild = thePlayer; } else { leftChild = 2 * matchNode - n + 1 + lowExt; rightChild = leftChild + 1; } } tree[matchNode] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild; // 第二场比赛的特例 if (matchNode == n - 1 && n % 2 == 1) { matchNode /= 2; // 移到父级 tree[matchNode] = (player[tree[n - 1]] <= player[lowExt + 1]) ? tree [n - 1] : lowExt + 1; } // 打剩下的比赛 matchNode /= 2; // 移到父级 for (; matchNode >= 1; matchNode /= 2) tree[matchNode] = (player[tree[2 * matchNode]] <= player[tree[2 * matchNode + 1]]) ? tree[2 * matchNode] : tree[2 * matchNode + 1]; } template<typename T> void completeWinnerTree<T>::output() const { cout << "参赛人数 = " << numberOfPlayers << " lowExt = " << lowExt << " offset = " << offset << endl; cout << "完成的优胜者树指针是" << endl; for (int i = 1; i < numberOfPlayers; i++) cout << tree[i] << ' '; cout << endl; } #endif // !COMPLELEWINNERTREE_H