装载问题——BFS（队列式）分支界限法

代码

BFS即队列分支界限法代码如下：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef struct node{
	struct node* parent;	//父节点 
	int weight;				//权重 
	bool lchild;			//左儿子标志
	node(struct node* p,int w ,bool flag){
		this->parent = p;
		this->weight = w;
		this->lchild = flag;
	} 
}Node;

int c;				//最大装载重量
int n;				//装载个数
int bestw = 0; 			//最佳装载重量 
int Ew = 0;					//当前装载重量
int weight[100000];		//每个装载重量 
int r = 0;				//剩余装载数量 
Node *bestE = 0;		//最优解结点
Node *E = 0;			//当前结点 
int best[100000];		//最佳结点数组 
queue<Node*> q;

void Inqueue(int weight,bool flag,int i)
{
	if(i == n){//可行叶节点 
		if(weight == bestw){
			bestE = E;
			best[n] = flag;
		}
		return;
	}
	Node* node = new Node(E,weight,flag);
	q.push(node);		
}

int main()
{
	cout<<"请输入最大装载重量："<<endl; 
	cin>>c;
	cout<<"请输入装载个数："<<endl;
	cin>>n;
	cout<<"请输入各个装载重量："<<endl;
	for(int i = 1 ; i <= n ; i++){
		cin>>weight[i];
	}
	memset(best,0,sizeof(best));  
	
	for(int i = 2 ; i <= n ; i++){
		r += weight[i];
	}
	int i = 1;
	Node* rear = NULL;
	q.push(rear);
	while(1){
		int w = Ew + weight[i];
		if(w <= c){		//当前扩展结点总量小于最大装载量
			if(w > bestw){		//大于当前最优装载量 
				bestw = w;
			}
			Inqueue(w,true,i);				
		}
		//检查右结点
		if(Ew+r>bestw){
			Inqueue(Ew,false,i);	
		}
		//取下一个结点
		E = q.front();
		q.pop();
		if(E == NULL){		//该层的尾结点 
			if(q.empty()){	//队列为空跳出循环 
				break;
			}
			q.push(rear);
			i++;
			r -= weight[i]; 
			E = q.front();		//重新获取新的结点 
			q.pop(); 
		}
		Ew = E->weight;			//更新当前重量 
	}
	for(int j = n-1 ; j > 0 ; j--){
		best[j] = bestE->lchild;
		bestE = bestE->parent;
	} 
	cout<<"最佳装载方案为："<<endl;
	for(int j = 1 ; j <= n ; j++){
		if(best[j] == 1){
			cout<<j<<" ";
		}
	}
	cout<<endl;
	cout<<"最佳重量为：\n"<<bestw<<endl; 
	
	return 0;
 } 

截图