代码
BFS即队列分支界限法代码如下：
代码语言：javascript复制#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;
} 截图
