01背包分支要点

1、背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量 为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大？形式化描述：给定 c 0, wi 0, vi 0 , 1in.要求找一 n元向量(x1,x2,xn,), xi 0,1, ? Ewi xi A B,C C , D , E C , E C , J, K C F , G G , L, M G , M G N , O O /0-1 背包问题 分支限界法求解#include stdafx.h#include MaxHeap.h#include using namespace std;class Object

2、templatefriend 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 bbnodefriend Knap;templatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); private:bbnode * parent; / 指向父节点的指针bool LChild; / 左儿子

3、节点标识;templateclass HeapNodefriend Knap;public:operator Typep() constreturn uprofit;private:Typep uprofit, / 节点的价值上界profit;/节点所相应的价值Typew weight; / 节点所相应的重量int level;/活节点在子集树中所处的层序号bbnode *ptr; / 指向活节点在子集中相应节点的指针;templateclass Knaptemplatefriend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx

4、); public:Typep MaxKnapsack();private:MaxHeapHeapNode *H;Typep Bound(int i);void 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(Ty

5、pe &a,Type &b);templatevoid BubbleSort(Type a,int n);int main()int n = 3;/ 物品数int c = 30;/ 背包容量int p = 0,45,25,25;/物品价值 下标从 1 开始int w = 0,16,15,15;/ 物品重量 下标从 1 开始int bestx4;/ 最优解cout 背包容量为： cendl;cout 物品重量和价值分别为： endl;for(int i=1; i=n; i+) cout(wi,pi) ;coutendl;cout 背包能装下的最大价值为： Knapsack(p,w,c,n,bes

6、tx)endl;cout 此背包问题最优解为 :endl;for(int i=1; i=n; i+)coutbestxi ;coutendl;return 0;templateTypep Knap:Bound(int i)/计算节点所相应价值的上界Typew cleft = c-cw; / 剩余容量高Typep b = cp;/ 价值上界/ 以物品单位重量价值递减序装填剩余容量while(i=n & wi=cleft)cleft -= wi;b += pi;i+;/ 装填剩余容量装满背包if(i=n)b += pi/wi*cleft;return b;/ 将一个活节点插入到子集树和优先队列中t

7、emplatevoid Knap:AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)bbnode *b = new bbnode;b-parent = E;b-LChild = ch;HeapNode N;N.uprofit = up;N.profit = cp;N.weight = cw;N.level = lev;N.ptr = b;H-Insert(N);/ 优先队列式分支限界法，返回最大价值， bestx 返回最优解 templateTypep Knap:MaxKnapsack()H = new MaxHeapHeapNode

8、(1000);/ 为 bestx 分配存储空间bestx = new intn+1;/ 初始化int i = 1;E = 0;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)/ 右子树可能

9、含有最优解 AddLiveNode(up,cp,cw,false,i+1);/ 取下一扩展节点 HeapNode N;H-DeleteMax(N);E = 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 返回最优解 templateTypep Knapsack(Typep p,Typew w,Typew c,int n, int bestx) /

10、 初始化Typew W = 0; / 装包物品重量Typep P = 0; / 装包物品价值/ 定义依单位重量价值排序的物品数组Object *Q = new Objectn;for(int i=1; i=n; i+)/ 单位重量价值数组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;for(int i=1; i=n; i+)

11、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(); for(int j=1; j=n; j+)bestxQj-1.ID = K.bestxj;delete Q;delete K.w;delete K.p;delete K.bestx;return bestp;templatevoid BubbleSort(Type a,int n)/ 记录一次遍历中是否有元素的交换bool exchange;for(int i=0; in-1;i+)exchange = false ;for(int j=i