算法设计与分析——分支限界法——装载问题

谁践踏了优雅 2022-10-05 13:52 140阅读 0赞

有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。

容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。  
(1)首先将第一艘轮船尽可能装满；  
(2)将剩余的集装箱装上第二艘轮船。  
**思想**：  
在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。

活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。

节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r<bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。

为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。

找到最优值后，可以根据parent回溯到根节点，找到最优解。

优先队列写法：

#include<iostream>
    #include<queue>//优先队列的头文件
    using namespace std;
    //子集树中节点的定义
    class bbnode{
         
    	public:
    		bbnode *parent;//指向父节点的指针 
    		bool Lchild;//是否是左孩子结点的标记 
    };
    //优先队列中节点的定义 
    class  HeapNode{
        
    	public:
    	bbnode *ptr;  //指向活结点在子集树中相应节点的指针
    	int uweight;  //活结点的优先级(上界) 
    	//优先级的定义：从根节点到节点x的路径相应的载重量加上剩余集装箱的重量之和
    	int level;   //活结点在子集树中所处的层次 
    }; 
    struct compare{
        
    	bool const operator()(HeapNode *&a,HeapNode *&b){
        
    		return (a->uweight) < (b->uweight);//最大堆 
    		
    	}
    };
    //该函数是将新产生的活结点加入到子集树中，并将这个节点插入到表示活结点优先队列的最大堆中 
    void AddLiveNode(priority_queue<HeapNode*,vector<HeapNode*>,compare> &Q,bbnode *parent,bool isLeft,int uWeight,int level)
    {
        
    	//先在子集树中建立这个节点
    	bbnode *b = new bbnode;
    	b->parent = parent;
    	b->Lchild = isLeft;
    	
    	//再在优先队列中新建一个节点
    	HeapNode *h = new HeapNode;
    	h->ptr = b;//将刚在添加到子集树中的新节点b再赋值给将要添加到优先队列中的节点h 
    	h->uweight = uWeight;
    	h->level = level; 
    	//将新建的节点添加到优先队列
    	Q.push(h); 
    	 	 
    }
    
    int MaxLoading(int *weight,int n,int *bestx,int c)
    {
        
    	priority_queue<HeapNode*,vector<HeapNode*>,compare> Heap;
    	int i=0;// 表示当前所在子集树的层次
    	int now_weight=0;//表示当前已装载的重量
    	int node_priority=0; //优先级————装载的最大上界=当前装载量+剩余集装箱的重量
    	
    	HeapNode *H;//用于保存从优先队列出来的节点 
    	bbnode *B;//子集树上的扩展节点
    	int *remains; //剩余集装箱 ， 记载未装的货物
    	remains = new int[n];
    	remains[n-1]=0;//当到达最后的叶子节点时，没有剩余的货物 
    	for(int j=n-2;j>=0;j--){
        	//计算当到达指定层时的剩余数组 
    		remains[j]=remains[j+1]+weight[j+1];
    	}
    	 
    	 while(i!=n)//没有到达叶子节点时 ,到达第i层 
    	 {
        
    	 	if(now_weight+weight[i]<=c)//即当前的重量能够装的下  =进入左子树 左孩子 
    		 {
        
    		 	node_priority=(now_weight+weight[i]) +remains[i];//优先级 =当前装载量+剩余集装箱的重量
    		 	AddLiveNode(Heap,B,true,node_priority,i+1);
    		 	
    		 }
    		// 进入右子树  右孩子 
    		  
    		  	node_priority=(now_weight) +remains[i];//优先级 =当前装载量+剩余集装箱的重量
    		 	AddLiveNode(Heap,B,false,node_priority,i+1);
    		  
    		  
    		H = Heap.top();		//查询优先队列队头结点 
    		Heap.pop();		//队头结点出队 
    		i=H->level;
    		B=H->ptr;	//记录当前到达的结点 
    		now_weight=H->uweight - remains[i-1];		//计算当前已经装载量  
    	  }
    	  
    	  
    	 	// 记录已装载货物 
    	for(int j=n-1;j>=0;j--){
        
    		bestx[j]=B->Lchild? 1:0;
    		B=B->parent;
    	}
    	return now_weight; 		//返回最优装载量  
     } 
    int main()
    {
        
    	int n;			//货物数  
    	int shipNum;			//货船数量 
    	int bestw;  			//最优装载量 
    	
    	int weight[n];			//货物总重量 
    	int bestx[n];			//最优的装载序列 
    	int c1=0;				//第一艘船的装载重量 
    	int c2=0;				//第二艘船的装载重量 
    	cout<<"请输入货物数：";
    	cin>>n;
    	cout<<"请输入货船的数量：";
    	cin>>shipNum;
    	cout<<"请输入货物的重量序列：";
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>weight[i];
    	 }
    	 cout<<"请输入两艘船的载重量：";
    	 cin>>c1>>c2;
    	 int maxc=0;//船的最大装载重量 
    	 int sumc=c1+c2;//船的装载重和 
    	 
    	 if(c1>c2)
    	 	maxc=c1;
    	else 
    		maxc=c2;
    		 
    	int maxweight=0;//货物中的最大重量
    	int sumweight=0;				//货船总重量 
    	for(int i=0;i<n;i++)
    	{
        
    		if(weight[i]>maxweight)
    		{
        
    			maxweight=weight[i];
    		}
    		sumweight+=weight[i];
    	 }
    	 
    	 if(maxweight>maxc)
    	 {
        
    		printf("货物重量超过货船的载重量，无法装载！");
    		return 0;
    	  } 
    	  
    	  if(sumweight>sumc){
        
    		printf("货物总重量超过货船的总载重量，无法装载！");
    		return 0;
    	}
    	MaxLoading(weight,n,bestx,c1);
    	cout<<"装载序列为："; 
    	for(int i=0;i<n;i++)
    	{
        
    		cout<<bestx[i]<<" ";
    	 }
    	cout<<endl;
    	cout<<"第1艘船的最优装载量为："<<MaxLoading(weight,n,bestx,c1)<<endl;
    	
    	 
    	 cout<<"装载的货物为：";
    	for(int i=0;i<n;i++)
    	{
        
    		if(bestx[i]!=0)
    		cout<<weight[i]<<" ";
    	}
    	cout<<endl;
    	cout<<"第2艘船的最优装载量为："<<sumweight-MaxLoading(weight,n,bestx,c1)<<endl;
    		 cout<<"装载的货物为：";
    	for(int i=0;i<n;i++)
    	{
        
    		if(bestx[i]!=1)
    		cout<<weight[i]<<" ";
    	}
    	
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
堆写法：

#include<iostream>
    #include<queue>//优先队列的头文件
    using namespace std;
    
    class bbnode{
         
    	public:
    		bbnode *parent;//指向父节点的指针 
    		bool Lchild;//是否是左孩子结点的标记 
    };
    //优先队列中节点的定义 
    class  HeapNode{
        
    	public:
    	operator double() const{
        return uweight;}
    	int operator <= (HeapNode hn) const{
        return uweight<=hn.uweight;	}
    	int operator <	(HeapNode hn) const{
        return uweight<hn.uweight;	}
    	int operator >= (HeapNode hn) const{
        return uweight>=hn.uweight;	}
    	int operator >	(HeapNode hn) const{
        return uweight>hn.uweight;	}
    	int operator == (HeapNode hn) const{
        return uweight==hn.uweight;	}
    	HeapNode(){
        }
    	bbnode *ptr;  //指向活结点在子集树中相应节点的指针
    	int uweight;  //活结点的优先级(上界) 
    	//优先级的定义：从根节点到节点x的路径相应的载重量加上剩余集装箱的重量之和
    	int level;   //活结点在子集树中所处的层次 
    }; 
    class MaxHeap
    {
        
    public:
    	MaxHeap(int n);    //构造函数，N表示堆中能存储的最大元素的个数 
    	void Insert(HeapNode heapNode);  //向堆中插入一个结点 
    	void DeleteMax(HeapNode &heapNode);  //删除堆中的最大结点 
    private:
    	int size;            
    	HeapNode *MH;       
    	
    	void Delete(HeapNode &heapNode,int index);  //删除堆中标号为index的元素，index从1开始，即1表示最大元素 
    	void SiftUp(int index);          //将堆中标号为index的元素，向上调整，保证堆结构 
    	void SiftDown(int index);      //将堆中标号为index的元素，向下调整，保证堆结构 
    };
    
    MaxHeap::MaxHeap(int n)
    {
        
    	size=0;
    	MH=new HeapNode[n];
    }
    
    void MaxHeap::SiftUp(int index)
    {
        
    	if(index<=1)
    		return;
    	bool done=false;
    	do
    	{
        
    		if(MH[index]>MH[index/2])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    		
    		index=index/2;
    	}while(index>1&&!done);
    }
    
    void MaxHeap::SiftDown(int index)
    {
        
    	if(2*index>size)
    		return;
    	bool done=false;
    	do
    	{
        
    		index=2*index;
    		if(index+1<=size&&MH[index+1]>MH[index])
    			index=index+1;
    		if(MH[index/2]<MH[index])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    	}while(2*index<=size&&!done);
    }
    
    void MaxHeap::Insert(HeapNode heapNode)
    {
        
    	size+=1;
    	MH[size]=heapNode;
    	SiftUp(size);
    }
    
    void MaxHeap::Delete(HeapNode &heapNode,int index)
    {
        
    	if(index<1||index>size)
    	{
        
    		return;
    	}
    	HeapNode x=MH[index],y=MH[size];
    	heapNode=MH[index];
    	size-=1;
    	if(index==size+1)
    		return;
    	MH[index]=y;//将原来堆中的最后一个放到要被删除的位置，再继续调整堆 
    	if(y>=x)
    		SiftUp(index);
    	else
    		SiftDown(index);
    }
    
    void MaxHeap::DeleteMax(HeapNode &heapNode)
    {
        
    	Delete(heapNode,1);
    }
    //子集树中节点的定义
    
    
    //该函数是将新产生的活结点加入到子集树中，并将这个节点插入到表示活结点优先队列的最大堆中 
    void AddLiveNode(MaxHeap &Q,bbnode *parent,bool isLeft,int uWeight,int level)
    {
        
    	//先在子集树中建立这个节点
    	bbnode *b = new bbnode;
    	b->parent = parent;
    	b->Lchild = isLeft;
    	
    	//再在优先队列中新建一个节点
    	HeapNode H;
    	H.ptr = b;//将刚在添加到子集树中的新节点b再赋值给将要添加到优先队列中的节点h 
    	H.uweight = uWeight;
    	H.level = level; 
    	//将新建的节点添加到优先队列
    	Q.Insert(H); 
    	 	 
    }
    
    int MaxLoading(int *weight,int n,int *bestx,int c)
    {
        
    	MaxHeap *Maxhp=new MaxHeap(100);;
    	int i=0;// 表示当前所在子集树的层次
    	int now_weight=0;//表示当前已装载的重量
    	int node_priority=0; //优先级————装载的最大上界=当前装载量+剩余集装箱的重量
    	
    	HeapNode H;//用于保存从优先队列出来的节点 
    	bbnode *B;//子集树上的扩展节点
    	int *remains; //剩余集装箱 ， 记载未装的货物
    	remains = new int[n];
    	remains[n-1]=0;//当到达最后的叶子节点时，没有剩余的货物 
    	for(int j=n-2;j>=0;j--){
        	//计算当到达指定层时的剩余数组 
    		remains[j]=remains[j+1]+weight[j+1];
    	}
    	 
    	 while(i!=n)//没有到达叶子节点时 ,到达第i层 
    	 {
        
    	 	if(now_weight+weight[i]<=c)//即当前的重量能够装的下  =进入左子树 左孩子 
    		 {
        
    		 	node_priority=(now_weight+weight[i]) +remains[i];//优先级 =当前装载量+剩余集装箱的重量
    		 	AddLiveNode(*Maxhp,B,true,node_priority,i+1);
    		 	
    		 }
    		// 进入右子树  右孩子 
    		  
    		  	node_priority=(now_weight) +remains[i];//优先级 =当前装载量+剩余集装箱的重量
    		 	AddLiveNode(*Maxhp,B,false,node_priority,i+1);
    		  
    		  
    	Maxhp->DeleteMax(H);		//查询优先队列队头结点 
    	
    		i=H.level;
    		B=H.ptr;	//记录当前到达的结点 
    		now_weight=H.uweight - remains[i-1];		//计算当前已经装载量  
    	  }
    	  
    	  
    	 	// 记录已装载货物 
    	for(int j=n-1;j>=0;j--){
        
    		bestx[j]=B->Lchild? 1:0;
    		B=B->parent;
    	}
    	return now_weight; 		//返回最优装载量  
     } 
    int main()
    {
        
    	int n;			//货物数  
    	int shipNum;			//货船数量 
    	int bestw;  			//最优装载量 
    	
    	int weight[n];			//货物总重量 
    	int bestx[n];			//最优的装载序列 
    	int c1=0;				//第一艘船的装载重量 
    	int c2=0;				//第二艘船的装载重量 
    	cout<<"请输入货物数：";
    	cin>>n;
    	cout<<"请输入货船的数量：";
    	cin>>shipNum;
    	cout<<"请输入货物的重量序列：";
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>weight[i];
    	 }
    	 cout<<"请输入两艘船的载重量：";
    	 cin>>c1>>c2;
    	 int maxc=0;//船的最大装载重量 
    	 int sumc=c1+c2;//船的装载重和 
    	 
    	 if(c1>c2)
    	 	maxc=c1;
    	else 
    		maxc=c2;
    		 
    	int maxweight=0;//货物中的最大重量
    	int sumweight=0;				//货船总重量 
    	for(int i=0;i<n;i++)
    	{
        
    		if(weight[i]>maxweight)
    		{
        
    			maxweight=weight[i];
    		}
    		sumweight+=weight[i];
    	 }
    	 
    	 if(maxweight>maxc)
    	 {
        
    		printf("货物重量超过货船的载重量，无法装载！");
    		return 0;
    	  } 
    	  
    	  if(sumweight>sumc){
        
    		printf("货物总重量超过货船的总载重量，无法装载！");
    		return 0;
    	}
    	
    	MaxLoading(weight,n,bestx,c1);
    	
    	cout<<"装载序列为："; 
    	for(int i=0;i<n;i++)
    	{
        
    		cout<<bestx[i]<<" ";
    	 }
    	cout<<endl;
    	cout<<"第1艘船的最优装载量为："<<MaxLoading(weight,n,bestx,c1)<<endl;
    	
    	 
    	 cout<<"装载的货物为：";
    	for(int i=0;i<n;i++)
    	{
        
    		if(bestx[i]!=0)
    		cout<<weight[i]<<" ";
    	}
    	cout<<endl;
    	cout<<"第2艘船的最优装载量为："<<sumweight-MaxLoading(weight,n,bestx,c1)<<endl;
    		 cout<<"装载的货物为：";
    	for(int i=0;i<n;i++)
    	{
        
    		if(bestx[i]!=1)
    		cout<<weight[i]<<" ";
    	}
    	
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221005/39b8266942b54d58ae3c2b39cfcd1571.png