# 装载问题－－队列式分支界限法

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

typedef struct Node{
int weight;
struct Node *parent;
bool choice;
}Node;

const int n = 10;
const int c= 0;
int w[n+1] = {0};
int bestx[n+1] = {0};
int bestw = 0;
queue<Node*> que;
Node *best_node = NULL;

void initParament()
{

}

void EnQueue(int i, int wt, Node *parent, bool choice)
{
if( i == n){
if( wt == bestw ){
best_node = parent;
bestx[n] = choice;
}
return;
}

Node *node = NULL;
node = new Node;
node->weight = wt;
node->parent = parent;
node->choice = choice;

que.push(node);
}

{
Node *current = 0;
int i = 1;
int current_weight = 0;

int rw = 0;
for(int i=2; i<=n; i++){
rw += w[i];
}
que.push(0);

while(true){
int wt = current_weight + w[i];
if( wt <= c ){
bestw = max(bestw, wt);
EnQueue(i, wt, current, true);
}

if( current_weight + rw > bestw ){
EnQueue(i, current_weight, current, false);
}
current = que.front();
que.pop();
if( current == NULL ){
if( que.empty() ){
break;
}
que.push(0);

current = que.front();
que.pop();
current_weight = current->weight;
rw -= w[i];
i++;
}

}

for(int i=n-1; i>=0; i++){
bestx[i] = best_node->choice;
best_node = best_node->parent;
}
}

int main()
{
initParament();