0036算法笔记【分支限界法】0-1背包问题

问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c0,wi0,vi0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。算法设计首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。例如：0-1背包问题，当n=3时，w={16,15,15},p={45,25,25},c=30。优先队列式分支限界法：处理法则:价值大者优先。{}—{A}—{B,C}—{C，D，E}—{C，E}—{C，J，K}—{C}—{F，G}—{G，L，M}—{G，M}—{G}—{N，O}—{O}—{}算法代码实现如下：1、MaxHeap.h[cpp]viewplaincopy1.templateclassT2.classMaxHeap3.{4.public:5.MaxHeap(intMaxHeapSize=10);6.~MaxHeap(){delete[]heap;}7.intSize()const{returnCurrentSize;}8.9.TMax()10.{//查11.if(CurrentSize==0)12.{13.throwOutOfBounds();14.}15.returnheap[1];16.}17.18.MaxHeapT&Insert(constT&x);//增19.MaxHeapT&DeleteMax(T&x);//删20.21.voidInitialize(Ta[],intsize,intArraySize);22.23.private:24.intCurrentSize,MaxSize;25.T*heap;//elementarray26.};27.28.templateclassT29.MaxHeapT::MaxHeap(intMaxHeapSize)30.{//Maxheapconstructor.31.MaxSize=MaxHeapSize;32.heap=newT[MaxSize+1];33.CurrentSize=0;34.}35.36.templateclassT37.MaxHeapT&MaxHeapT::Insert(constT&x)38.{//Insertxintothemaxheap.39.if(CurrentSize==MaxSize)40.{41.coutnospace!endl;42.return*this;43.}44.45.//寻找新元素x的位置46.//i——初始为新叶节点的位置，逐层向上，寻找最终位置47.inti=++CurrentSize;48.while(i!=1&&xheap[i/2])49.{50.//i不是根节点，且其值大于父节点的值，需要继续调整51.heap[i]=heap[i/2];//父节点下降52.i/=2;//继续向上，搜寻正确位置53.}54.55.heap[i]=x;56.return*this;57.}58.59.templateclassT60.MaxHeapT&MaxHeapT::DeleteMax(T&x)61.{//Setxtomaxelementanddeletemaxelementfromheap.62.//checkifheapisempty63.if(CurrentSize==0)64.{65.coutEmptyheap!endl;66.return*this;67.}68.69.x=heap[1];//删除最大元素70.//重整堆71.Ty=heap[CurrentSize--];//取最后一个节点，从根开始重整72.73.//findplaceforystartingatroot74.inti=1,//currentnodeofheap75.ci=2;//childofi76.77.while(ci=CurrentSize)78.{79.//使ci指向i的两个孩子中较大者80.if(ciCurrentSize&&heap[ci]heap[ci+1])81.{82.ci++;83.}84.//y的值大于等于孩子节点吗？85.if(y=heap[ci])86.{87.break;//是，i就是y的正确位置，退出88.}89.90.//否，需要继续向下，重整堆91.heap[i]=heap[ci];//大于父节点的孩子节点上升92.i=ci;//向下一层，继续搜索正确位置93.ci*=2;94.}95.96.heap[i]=y;97.return*this;98.}99.100.templateclassT101.voidMaxHeapT::Initialize(Ta[],intsize,intArraySize)102.{//Initializemaxheaptoarraya.103.delete[]heap;104.heap=a;105.CurrentSize=size;106.MaxSize=ArraySize;107.108.//从最后一个内部节点开始，一直到根，对每个子树进行堆重整109.for(inti=CurrentSize/2;i=1;i--)110.{111.Ty=heap[i];//子树根节点元素112.//findplacetoputy113.intc=2*i;//parentofcistarget114.//locationfory115.while(c=CurrentSize)116.{117.//heap[c]shouldbelargersibling118.if(cCurrentSize&&heap[c]heap[c+1])119.{120.c++;121.}122.//canweputyinheap[c/2]?123.if(y=heap[c])124.{125.break;//yes126.}127.128.//no129.heap[c/2]=heap[c];//movechildup130.c*=2;//movedownalevel131.}132.heap[c/2]=y;133.}134.}2、6d5.cpp[cpp]viewplaincopy1.//0-1背包问题分支限界法求解2.#includestdafx.h3.#includeMaxHeap.h4.#includeiostream5.usingnamespacestd;6.7.classObject8.{9.templateclassTypew,classTypep10.friendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);11.public:12.intoperator=(Objecta)const13.{14.returnd=a.d;15.}16.private:17.intID;18.floatd;//单位重量价值19.};20.21.templateclassTypew,classTypepclassKnap;22.23.classbbnode24.{25.friendKnapint,int;26.templateclassTypew,classTypep27.friendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);28.private:29.bbnode*parent;//指向父节点的指针30.boolLChild;//左儿子节点标识31.};32.33.templateclassTypew,classTypep34.classHeapNode35.{36.friendKnapTypew,Typep;37.public:38.operatorTypep()const39.{40.returnuprofit;41.}42.private:43.Typepuprofit,//节点的价值上界44.profit;//节点所相应的价值45.Typewweight;//节点所相应的重量46.intlevel;//活节点在子集树中所处的层序号47.bbnode*ptr;//指向活节点在子集中相应节点的指针48.};49.50.templateclassTypew,classTypep51.classKnap52.{53.templateclassTypew,classTypep54.friendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);55.public:56.TypepMaxKnapsack();57.private:58.MaxHeapHeapNodeTypep,Typew*H;59.TypepBound(inti);60.voidAddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev);61.62.bbnode*E;//指向扩展节点的指针63.Typewc;//背包容量64.intn;//物品数65.66.Typew*w;//物品重量数组67.Typep*p;//物品价值数组68.Typewcw;//当前重量69.70.Typepcp;//当前价值71.int*bestx;//最优解72.};73.74.templateclassType75.inlinevoidSwap(Type&a,Type&b);76.77.templateclassType78.voidBubbleSort(Typea[],intn);79.80.intmain()81.{82.intn=3;//物品数83.intc=30;//背包容量84.intp[]={0,45,25,25};//物品价值下标从1开始85.intw[]={0,16,15,15};//物品重量下标从1开始86.intbestx[4];//最优解87.88.cout背包容量为：cendl;89.cout物品重量和价值分别为：endl;90.91.for(inti=1;i=n;i++)92.{93.cout(w[i],p[i]);94.}95.coutendl;96.97.cout背包能装下的最大价值为：Knapsack(p,w,c,n,bestx)endl;98.cout此背包问题最优解为:endl;99.for(inti=1;i=n;i++)100.{101.coutbestx[i];102.}103.coutendl;104.return0;105.}106.107.templateclassTypew,classTypep108.TypepKnapTypew,Typep::Bound(inti)//计算节点所相应价值的上界109.{110.Typewcleft=c-cw;//剩余容量高111.Typepb=cp;//价值上界112.//以物品单位重量价值递减序装填剩余容量113.while(i=n&&w[i]=cleft)114.{115.cleft-=w[i];116.b+=p[i];117.i++;118.}119.120.