最优装载问题1.doc

n1ciwi(20)21ncn1000c655352nw1w2wnnn0wi 1000i=1,2,n31Case #12bestnleftcbestnleftcbestn30-1x1x2xnx1x2xnbestnxi=1ixi=0ibestn4010403502110011n0-11103 5040 10 405 3710 30 24 35 40Case 12 0110Case 22 310100 #include /template class MaxHeap; /template class HeapNode; class bbnode friend void AddLiveNode(MaxHeap&,bbnode*,int,int,int); friend int MaxLoading(int*,int,int ,int *); /friend class adjacencygraph; private: bbnode *parent; / int Lchild; / ; / /template class HeapNode friend void AddLiveNode(MaxHeap&,bbnode*,int,int,int); friend int MaxLoading(int*,int,int,int *); public: operator int() const return uweight; / private: bbnode *ptr; / int uweight; / int level; / ; /template class MaxHeap friend void AddLiveNode(MaxHeap&,bbnode *,int,int,int ); friend int Maxloading(int*,int,int,int*); private: int m; int sz; HeapNode *Hx; public: MaxHeap(int sz) Hx=new HeapNodesz; m=0; /MaxHeap()delete Hx; void insert(HeapNode N) Hxm+1=N; Hxm+1.ptr=N.ptr; Hxm+1.uweight=N.uweight; Hxm+1.level=N.level; m+; HeapNode DeleteMax(HeapNode N) for(int p=1;p=m;p+) int temp=Hx0; / coutHxptemp) temp=Hxp; N=Hxp; N.ptr=Hxp.ptr; N.uweight=Hxp.uweight; N.level=Hxp.level; / coutN.levelendl; return N; ; / / template /H void AddLiveNode(MaxHeap&H,bbnode *E,int wt,int ch,int lev) bbnode *b=new bbnode; b-parent=E; b-Lchild=ch; /coutLchildLchildendl; HeapNode N; N.uweight=wt; N.level=lev; N.ptr=b; H.insert(N); /coutN.levelendl; / / template int MaxLoading(int w,int c,int n,int bestw) MaxHeap H(20); int *r=new intn+1; rn=0; for(int j=n-1;j0;j-) rj=rj+1+wj+1; int i=1; bbnode *E=0; int Ew=0; while(i!=n+1) if(Ew+wi=c) / AddLiveNode(H,E,Ew+wi+ri,1,i+1); AddLiveNode(H,E,Ew+ri,0,i+1); / HeapNode N; N=H.DeleteMax(N); i=N.level; E=N.ptr; Ew=N.uweight-ri-1; coutN.weightN.uweightEw0;x-) bestwx=E-Lchild; /coutparent; / coutEw IS Ewn; int *bestw=new intn+1; int *w=new intn+1; /HeapNode; /MaxHeapHeapNode H; coutPlease input the weight of every bag:endl; for(int j=1;jwj; coutPlease input the maximum we