分支限界法用于解决装载问题。

简介：
#include #include #include #includeusing namespace std;ifstream infile;ofstream outfile;class Node { friend int func(int*, int, int, int*); public: int ID; double weight;//物品的重量 }; bool comp1(Node a, Node b) //定义比较规则{ return a.weight > b.weight; } class Load;class bbnode;class Current { friend Load; friend struct Comp2; private: int upweight;//重量上界 int weight;//结点相应的重量 int level;//活结点在子集树中所处的层次 bbnode* ptr;//指向活结点在子集树中相应结点的指针 }; struct Comp2{ bool operator () (Current *x, Current *y) { return x->upweightupweight; }};class Load { friend int func(int*, int, int, int*); public: int Max0(); private: priority_queue, Comp2>H;//利用优先队列（最大堆）储存 int limit(int i); void AddLiveNode(int up, int cw, bool ch, int level); bbnode *P;//指向扩展结点的指针 int c;//背包的容量 int n;//物品的数目 int *w;//重量数组 int cw;//当前装载量 int *bestx;//最优解方案数组 }; class bbnode { friend Load; friend int func( int*, int, int, int*); bbnode* parent; bool lchild; }; //结点中有双亲指针以及左儿子标志int Load::limit(int i) //计算结点所相应重量的上界 { int left,a; left= c - cw;//剩余容量 a = cw; //b是重量上界，初始值为已经得到的重量 while (i <= n && w[i] <= left) { left -= w[i]; a += w[i]; i++; } return a;} void Load::AddLiveNode(int up, int cw, bool ch, int level) //将一个新的活结点插入到子集树和优先队列中{ bbnode *b = new bbnode; b->parent = P; b->lchild = ch; Current* N = new Current; N->upweight = up; N->weight = cw; N->level = level; N->ptr = b ; H.push(N);}