01背包分支要点Word格式.docx

1、CF，GG，L，MG，MGN，OO /0-1背包问题 分支限界法求解 #include stdafx.h MaxHeap.h#include using namespace std;class Object template friend Typep Knapsack（Typep p,Typew w,Typew c,int n, int bestx）; public: int operator =a.d; private: int ID; float d;/单位重量价值 ;template class Knap;class bbnode friend Knap; bbnode * parent

2、; /指向父节点的指针 bool LChild; /左儿子节点标识 class HeapNode Typew,Typep operator Typep（） const return uprofit; Typep uprofit, /节点的价值上界 profit; /节点所相应的价值 Typew weight; /节点所相应的重量 int level; /活节点在子集树中所处的层序号 bbnode *ptr; /指向活节点在子集中相应节点的指针 class Knap Typep MaxKnapsack（）; MaxHeapHeapNode *H; Typep Bound（int i）; void

3、 AddLiveNode（Typep up,Typep cp,Typew cw,bool ch,int lev）; bbnode *E; /指向扩展节点的指针 Typew c; /背包容量 int n; /物品数 Typew *w; /物品重量数组 Typep *p; /物品价值数组 Typew cw; /当前重量 Typep cp; /当前价值 int *bestx; /最优解 template inline void Swap（Type &a,Type &b）;void BubbleSort（Type a,int n）;int main（） int n = 3;/物品数 int c = 3

4、0;/背包容量 int p = 0,45,25,25;/物品价值 下标从1开始 int w = 0,16,15,15;/物品重量 下标从1开始 int bestx4;/最优解 cout背包容量为：cendl;物品重量和价值分别为： for（int i=1; i=n; i+） （wi,pi） 背包能装下的最大价值为：Knapsack（p,w,c,n,bestx）此背包问题最优解为:bestxi return 0; Typep Knap:Bound（int i）/计算节点所相应价值的上界 Typew cleft = c-cw; /剩余容量高 Typep b = cp; /价值上界 /以物品单位重量

5、价值递减序装填剩余容量 while（i=n & wi=cleft） cleft -= wi; b += pi; i+; /装填剩余容量装满背包 if（i=n） b += pi/wi*cleft; return b;/将一个活节点插入到子集树和优先队列中 void Knapparent = E;LChild = ch; HeapNodeInsert（N）;/优先队列式分支限界法，返回最大价值，bestx返回最优解 MaxKnapsack（） H = new MaxHeap（1000）; /为bestx分配存储空间 bestx = new intn+1; /初始化 int i = 1; E = 0

6、; cw = cp = 0; Typep bestp = 0;/当前最优值 Typep up = Bound（1）; /搜索子集空间树 while（i!=n+1） /检查当前扩展节点的左儿子节点 Typew wt = cw + wi; if（wt bestp） bestp = cp + pi; AddLiveNode（up,cp+pi,cw+wi,true,i+1）; up = Bound（i+1）; /检查当前扩展节点的右儿子节点 if（up=bestp）/右子树可能含有最优解 AddLiveNode（up,cp,cw,false,i+1）; /取下一扩展节点 DeleteMax（N）; E

7、 = N.ptr; cw = N.weight; cp = N.profit; up = N.uprofit; i = N.level; /构造当前最优解 for（int j=n; j0; j-） bestxj = E-LChild; E = E-parent; return cp;/返回最大价值，bestx返回最优解 Typep Knapsack（Typep p,Typew w,Typew c,int n, int bestx） Typew W = 0; /装包物品重量 Typep P = 0; /装包物品价值 /定义依单位重量价值排序的物品数组 Object *Q = new Object

8、n; /单位重量价值数组 Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if（W=c） return P;/所有物品装包 /依单位价值重量排序 BubbleSort（Q,n）; /创建类Knap的数据成员 Knap K; K.p = new Typepn+1; K.w = new Typewn+1; K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; /调用MaxKnapsack求问题的最优解 Typep bestp = K.MaxKnapsack

9、（）; for（int j=1; j j+） bestxQj-1.ID = K.bestxj; delete Q; delete K.w; delete K.p; delete K.bestx; return bestp;void BubbleSort（Type a,int n） /记录一次遍历中是否有元素的交换 bool exchange; for（int i=0;n-1;i+） exchange = false ; for（int j=i+1;=n-1; if（aj=aj-1） Swap（aj,aj-1）; exchange = true; /如果这次遍历没有元素的交换,那么排序结束 if（false = exchange） break ;b） Type temp = a; a = b; b = temp;