学步园

      解01背包问题的第三种解法也终于被我攻破了，这个方法里面有许多和前面回溯相同的地方，结构基本相同，只是这里引入了一个大顶堆而已，所以如果综合前面的方法，再看这里的优先队列式解法的话会很容易理解。好了，不多说，下面是代码：

#include<iostream><br /> #include <algorithm><br /> #include "heap.h"<br /> using namespace std; </p> <p>class Knap<br /> {<br /> public:<br /> Knap(double *pp,double *ww,double cc,int nn)//构造函数<br /> {<br /> p=pp;<br /> w=ww;<br /> c=cc;<br /> n=nn;<br /> cw=0;<br /> cp=0;<br /> E=0;<br /> bestx=new int[n+1];<br /> H=init(100);<br /> }<br /> double knapsack();//找最优值的函数。<br /> double Bound(int i);//边界函数<br /> void AddLiveNode(double up,double cp,double cw,bool ch,int lev);<br /> int MaxKnapsack();</p> <p> void output()//输出最佳路径<br /> {<br /> for(int i=1;i<=n;i++)<br /> cout<<bestx[i]<<" ";<br /> cout<<endl;<br /> } </p> <p>private:<br /> double c; //背包容量<br /> int n; //物品总数<br /> double *w; //物品重量数组<br /> double *p; //物品价值数组<br /> double cw; //当前背包重量<br /> double cp; //当前背包价值<br /> bbnode *E; //指向扩展结点的指针<br /> int *bestx; //最优解结构<br /> HeapQueue H;</p> <p>}; </p> <p>class Object<br /> {<br /> public:<br /> int ID;<br /> double d;<br /> }; </p> <p>int cmp(Object a,Object b)//定于排序类型。<br /> {<br /> return a.d>b.d;//降序<br /> } </p> <p>double Knap::Bound(int i)<br /> { </p> <p> Object *Q=new Object[n+1];<br /> int j;<br /> for(j=1;j<=n;j++)<br /> {<br /> Q[j].ID=j;<br /> Q[j].d=1.0*p[j]/w[j];<br /> }<br /> sort(Q+1,Q+n+1,cmp);/*对数组Q排序。按cmp()方式排序。这里要注意是从Q[1]开始而不是从Q开始*/<br /> /*这里的Object 数组其实可以只创建一次就可以了，像现在这样每次调用Bound()都要创建并且对其进行排序，浪费资源，有待改进*/</p> <p>/*<br /> for(j=1;j<=n;j++)<br /> cout<<Q[j].ID<<" ";<br /> cout<<endl;<br /> */</p> <p> double cleft=c-cw;<br /> double b=cp;<br /> while(i<=n&&w[Q[i].ID]<=cleft)<br /> {<br /> cleft-=w[Q[i].ID];<br /> b+=p[Q[i].ID];<br /> i++;<br /> }<br /> if(i<=n)<br /> b+=1.0*p[Q[i].ID]*cleft/w[Q[i].ID];/*如果不能完整装入一个物品，则可以装入部分。*/<br /> return b;<br /> } </p> <p>double Knap::knapsack()<br /> {<br /> /*分支判断，如果背包容量足够大，就不用再回溯搜索了。*/<br /> int i;<br /> double W=0;<br /> double P=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> W+=w[i];<br /> P+=p[i];<br /> }<br /> if(W<=c) //如果背包够大的话那么最优解就是全部了。bestx[]=1；<br /> {<br /> for(int j=1;j<=n;j++)<br /> bestx[j]=1;<br /> return P;<br /> }<br /> /*如果背包容量不够大，则有最有的方案，使用优先队列方法。*/ </p> <p> return MaxKnapsack();<br /> } </p> <p>void Knap::AddLiveNode(double up,double cp,double cw,bool ch,int lev)<br /> {<br /> bbnode *b=new bbnode;<br /> b->parent=E;<br /> b->LChild=ch;<br /> HeapNode N;<br /> N.uprofit=up;<br /> N.profit=cp;<br /> N.weight=cw;<br /> N.level=lev;<br /> N.ptr=b;<br /> InsertMax(N,H);<br /> }<br /> int Knap::MaxKnapsack()<br /> {<br /> double bestp=0;//当前最优值<br /> double up=Bound(1);//价值上界<br /> // cout<<up<<endl;//输出为22<br /> int i=1;<br /> while(i != n + 1)<br /> {<br /> //double wt=cw+w[i];<br /> //cout<<wt<<endl;<br /> if(cw+w[i]<=c)<br /> {<br /> if(cp+p[i]>bestp)/*前面是cw+w[i]<=c，这里是当前价值加上这一物品的价值大于最优值时更新最优值bestp*/<br /> bestp=cp+p[i];<br /> AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);//激活这一结点<br /> }<br /> up=Bound(i+1);<br /> //检查当前扩展结点的右儿子结点<br /> if(up>=bestp)<br /> AddLiveNode(up,cp,cw,false,i+1);<br /> //取出下一个扩展结点<br /> HeapNode N;<br /> N=DeleteMax(H);<br /> E=N.ptr;<br /> cw=N.weight;<br /> cp=N.profit;<br /> up=N.uprofit;<br /> i=N.level;<br /> }</p> <p> //构造当前左右解<br /> for(int j=n;j>0;j--)<br /> {<br /> bestx[j]=E->LChild;<br /> E=E->parent;<br /> }<br /> return cp;<br /> }</p> <p>int main()<br /> {<br /> int n=4;<br /> double c=7;//背包容量<br /> /*注意点，这里的数组p[]和w[]的第一个元素是-100，这是因为我在操作过程中都是从数组元素的1开始的，而我们知道数组中第一个元素是0号元素，所以我这里用-100填上*/<br /> double p[]={-100,9,10,7,4};//物品价值<br /> double w[]={-100,3,5,2,1};//物品重量<br /> Knap k=Knap(p,w,c,n);<br /> cout<<k.knapsack()<<endl;<br /> k.output();<br /> return 1;<br /> }

今天才发现好像少发了一个头文件，现在补上

struct bbnode<br /> {<br /> bbnode *parent;<br /> bool LChild;<br /> }; </p> <p>struct HeapNode<br /> {<br /> bbnode *ptr; //指向活结点在子集树中相应结点的指针 </p> <p> double weight; //结点所相应的重量<br /> double uprofit, //结点的价值上限<br /> profit; //结点所相应的价值<br /> int level; //活结点在子集树中所处的层序号<br /> };<br /> /****************************************************************************/ </p> <p>/****************************************************************************/<br /> typedef HeapNode ElemType;<br /> #define MaxData 32767 </p> <p>typedef struct Heap<br /> {<br /> int capacity;<br /> int size;<br /> HeapNode *Elem; </p> <p>}Heap,*HeapQueue; </p> <p>HeapQueue init(int maxElem)<br /> {<br /> HeapQueue H=new Heap;<br /> H->capacity=maxElem;<br /> H->size=0;<br /> H->Elem=new HeapNode[maxElem+1];<br /> H->Elem[0].uprofit=MaxData;<br /> return H;<br /> } </p> <p>void InsertMax(ElemType x,HeapQueue H)<br /> {<br /> int i;<br /> for(i=++H->size;H->Elem[i/2].uprofit<x.uprofit;i/=2)<br /> H->Elem[i]=H->Elem[i/2];//此时i还没有进行i/2操作<br /> H->Elem[i]=x;<br /> } </p> <p>ElemType DeleteMax(HeapQueue H)<br /> {<br /> int i,child;<br /> ElemType MaxElem,LastElem; //存储最大元素和最后一个元素。<br /> MaxElem=H->Elem[1]; //堆是从第1号元素开始的。<br /> LastElem=H->Elem[ H->size-- ]; //这里自动让size减少了。<br /> for(i = 1 ; i * 2 <= H->size ; i = child)<br /> {<br /> child=i * 2;<br /> /*在节点有左右子树的时候，可能存在一个大一个小的情况，这时候我们就要找出最小的；<br /> 如果Child = H->Size则表明他没有右子树，这时候就没有必要比较了。<br /> */<br /> if(child != H->size && H->Elem[child+1].uprofit>H->Elem[child].uprofit)<br /> child++;//找最大的子树<br /> if(LastElem.uprofit < H->Elem[child].uprofit)<br /> H->Elem[i]=H->Elem[child];<br /> }<br /> H->Elem[i]=LastElem;<br /> return MaxElem;<br /> }