#include "stdio.h"
#include "malloc.h"
//#define n 10
#define QueueSize 100 //假定預(yù)分配的隊(duì)列空間最多為100個(gè)元素  
typedef int DataType; //假定隊(duì)列元素的數(shù)據(jù)類型為字符
typedef struct node{
	DataType data;
	struct node *next;
}QueueNode;
typedef struct{
	QueueNode *front;  //頭指針
	QueueNode *rear;
}LinkQueue;
// 置隊(duì)列空
void Initial(LinkQueue *Q)
{//將順序隊(duì)列置空
    Q->front=Q->rear=NULL;
} 
//判隊(duì)列空
int IsEmpty(LinkQueue *Q)
{
    return Q->front==NULL&&Q->rear==NULL;
}
//進(jìn)隊(duì)列
void EnQueue(LinkQueue *Q,DataType x)
{//將元素x插入鏈隊(duì)列尾部
	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申請(qǐng)新結(jié)點(diǎn)
	p->data=x;
	p->next=NULL;
    if(IsEmpty(Q))
		Q->front=Q->rear=p;  //將x插入空隊(duì)列
	else 
	{ //x插入非空隊(duì)列的尾
		Q->rear->next=p;     //*p鏈到原隊(duì)尾結(jié)點(diǎn)后
		Q->rear=p;           //隊(duì)尾指針指向新的尾
	}
}
//出隊(duì)列
DataType DeQueue(LinkQueue *Q)
{
	DataType x;
	QueueNode *p;
	if(IsEmpty(Q))
	{
		printf("隊(duì)列為空");//下溢
		exit(1);
	}
	p=Q->front;                   //指向?qū)︻^結(jié)點(diǎn)
	x=p->data;                    //保存對(duì)頭結(jié)點(diǎn)的數(shù)據(jù)
	Q->front=p->next;             //將對(duì)頭結(jié)點(diǎn)從鏈上摘下
    if(Q->rear==p)//原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已為空
		Q->rear=NULL;
	free(p);   //釋放被刪隊(duì)頭結(jié)點(diǎn)
	return x;  //返回原隊(duì)頭數(shù)據(jù)
}
// 取隊(duì)列頂元素
DataType Front(LinkQueue *Q)
{
	if(IsEmpty(Q))
	{
		printf("隊(duì)列為空"); //下溢,退出運(yùn)行
		exit(1);
	}
	return Q->front->data;
}
void AddLiveNode(LinkQueue Q, DataType wt,DataType bestw, int i, int n)
{// 如果不是葉節(jié)點(diǎn)，則將節(jié)點(diǎn)權(quán)值w t加入隊(duì)列Q
	if (i == n) 
	{// 葉子
		if (wt>bestw) 
			bestw = wt;
	}
	else 
		EnQueue(&Q,wt); // 不是葉子
}
DataType MaxLoading(DataType w[], DataType c, int n)
{// 返回最優(yōu)裝載值
// 使用FIFO分枝定界算法
// 為層次1初始化
	DataType Ew = 0, // E-節(jié)點(diǎn)的權(quán)值
		bestw = 0; // 目前的最優(yōu)值
	int i = 1; // E-節(jié)點(diǎn)的層
	LinkQueue	 Q; // 活節(jié)點(diǎn)隊(duì)列
	EnQueue(&Q,-1); //標(biāo)記本層的尾部
	// 搜索子集空間樹(shù)
	while (1) {
		// 檢查E-節(jié)點(diǎn)的左孩子
		if (Ew + w[i] <= c) // x[i] = 1
			AddLiveNode(Q, Ew + w[i], bestw, i, n);	
		// 右孩子總是可行的
		AddLiveNode(Q, Ew, bestw, i, n); // x[i] = 0
			Ew=DeQueue(&Q); // 取下一個(gè)E-節(jié)點(diǎn)
		if (Ew == -1) 
		{ // 到達(dá)層的尾部
			if (IsEmpty(&Q)) 
				return bestw;
			EnQueue(&Q,-1); //添加尾部標(biāo)記
			Ew=DeQueue(&Q); // 取下一個(gè)E-節(jié)點(diǎn)
			i++;
		} // Ew的層
	}
}
void main()
{
	DataType w[10],c;
	//初始化w[n],c,n
	MaxLoading(w,c,10);
}