利用分支界限法解决装载问题

#include"d_random.h" #include"d_timer.h" #include<iostream> #include<queue> using namespace std; struct bbnode { bbnode *parent; int LChild; }; class HeapNode { public : friend bool operator<(const HeapNode& a, const HeapNode& b) { return (a.uweight<b.uweight); } bbnode *ptr; int uweight; int level; }; void AddLiveNode(priority_queue<HeapNode> &H,bbnode* E,int wt,int ch,int lev) { bbnode* b=new bbnode; b->parent=E; b->LChild=ch; HeapNode N; N.uweight=wt; N.level=lev; N.ptr=b; H.push(N); } int MaxLoading (int w[],int c,int n,int bestx[]) { priority_queue<HeapNode> H; int* r=new int[n+1]; r[n]=0; for(int j=n-1;j>0;j--) r[j]=r[j+1]+w[j+1]; int i=1; bbnode* E=0; int Ew=0; while(i!=n+1) { int wt=Ew+w[i]; if(wt<=c) { AddLiveNode(H,E,wt+r[i],1,i+1); } AddLiveNode(H,E,Ew+r[i],0,i+1); } HeapNode N; N=H.top(); H.pop(); i=N.level; E=N.ptr; Ew=N.uweight-r[i-1]; for(j=n;j>0;j--){ bestx[j]=E->LChild; E=E->parent; } return Ew; } int main() { timer t1;//定义时间 int bestx[100];//记录最优装载 int count=0; int weight;//重量 int i;//定义变量i int n=3;//定义25个集装箱 int c[2];//定义2艘船 int w[4]={0,10,40,40};//定义25个集装箱的重量,除掉w[0] randomNumber ran;//随机数 for(i=0;i<2;i++)//船的载重初始化为1000 { c[i]=50; } for(i=0;i<=n;i++) { bestx[i]=0;//初始化 } w[0]=0; /* for(i=1;i<=n;i++) {//随即生成n个集装箱的重量 w[i]=ran.random(40)+1; }*/ t1.start(); weight=MaxLoading(w,c[0],n,bestx); t1.stop(); cout<<"当前最优载重为："<<weight<<endl; cout<<"输出"<<n<<"集装箱的重量:"<<endl; for(i=0;i<n;i++) { if(i%10==0&&i!=0) cout<<endl; cout<<w[i+1]<<" "; } cout<<"所用的时间为："<<t1.time()<<endl; for(i=1;i<=n;i++){ if(bestx[i]==0) { count+=w[i]; } } if(count<=c[1]){ cout<<"货物装载情况(按排序后的集装箱顺序)："<<endl;; for(i=1;i<=n;i++){ if(bestx[i]==0) cout<<"货物"<<i<<"装载于第2艘船！"<<endl; else cout<<"货物"<<i<<"装载于第1艘船！"<<endl; } } else{ cout<<"无法装载！"; } cout<<endl; return 0; return 0; }