装载问题——优先级队列分支界限法

代码

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

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

struct cmp{
	bool operator()(Node *node1,Node *node2){
		return node1->weight<node2->weight;
	}
};

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

void AddNode(Node* parent,int weight,int lev,bool flag)
{
	Node* node = new Node(parent,weight,lev,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));  
	r[n] = 0;
	for(int i = n-1 ; i > 0 ; i--){
		r[i] = r[i+1]+weight[i+1];
	} 
	/*
	for(int i = 1 ; i <= n ; i++){
		cout<<r[i]<<" ";
	} 
	cout<<endl;*/
	
	//开始进行转载
	int i = 1;
	while(i != n+1){
		int w = Ew+weight[i];
		if(w <= c){//左儿子作为可行结点 
			AddNode(E,w+r[i],i+1,true);
		}
		//右儿子作为潜在可行结点 
		AddNode(E,Ew+r[i],i+1,false);
		E = q.top();
		q.pop();
		i = E->level;
		Ew = E->weight-r[i-1];
		cout<<i<<" "<<E->weight<<" "<<Ew<<endl;
	} 
	bestw = Ew; 
	for(int j = n ; j > 0 ; j--){
		best[j] = E->lchild;
		E = E->parent;
	} 
	
	cout<<"最佳装载方案为："<<endl;
	for(int j = 1 ; j <= n ; j++){
		if(best[j] == 1){
			cout<<j<<" ";
		}
	}
	cout<<endl;
	//cout<<"最佳重量为：\n"<<bestw<<endl; 
	
	return 0;
}

截图