#include<stdio.h>
#include<stdlib.h>
#define null 0
int P[5]={0,10,10,12,18};
int W[5]={0,2,4,6,9};
/*int N=4;
int M=15;*/
int LBB=0,UBB=0;


struct node
{
	int mark;
	int Parent;
	int Lever;
	int Tag;
	int CU;
	int PE;
	int UB;
	struct node *next;
};
struct node *head,*ANS,*newhead;




LUBOUND(int rw,int cp,int N,int K);//計算下界和上界的算法
NEWNODE(int par,int lev,int t,int cap,int prof,int ub,int mark);//生成一個新結點
struct node *LARGEST();//在活結點表中取一個具有最大UB值的結點作為下一個E-結點
FINISH(int L,int N);//打印答案
struct node *SEARCH(int m);//尋找滿足題意的結點
INSERT(struct node *node);//將E-結點插入活結點表中
int MAX(int m,int n);//取2數的最大值
insert(struct node *node);//生成結果結點表

//LC分枝—限界算法
LCKNAP(int M,int N,int e)
{
	int L,cap,prof;
	int i,mark=0;
	struct node *p;
	p=(struct node *)malloc(sizeof(struct node));
	p->mark=0;
	p->Parent=0;
	p->Lever=1;
	p->CU=M;
	p->PE=0;
	LUBOUND(M,0,N,1);
	L=LBB-e;
	p->UB=UBB;
	while(p->UB>=L)
	{
		insert(p);
		i=p->Lever;
		cap=p->CU;
		prof=p->PE;
		while(1)
		{
		if(i==N+1)
		{
			if(prof>L)
				 {
					 L=prof;
				 }
					 ANS=p;

			break;
		}
		else
		{
			if(cap>=W[i])
			{
				mark++;
				NEWNODE(p->mark,i+1,1,cap-W[i],prof+P[i],p->UB,mark);
			}
			LUBOUND(cap,prof,N,i+1);
			if(UBB>L)
			{
				mark++;
				NEWNODE(p->mark,i+1,0,cap,prof,UBB,mark);
				L=MAX(L,LBB-e);
			}
		}
		break;
		}
		if(head==null)
			break;
		else p=LARGEST(head);
	}
	FINISH(L,N);
}

int MAX(int m,int n)
{
	if(m>n) return m;
	else return n;
}


LUBOUND(int rw,int cp,int N,int k)
{
	int i,j,c;
	LBB=cp;
	c=rw;
	for(i=k;i<=N;i++)
	{
		if(c<W[i])
		{
			UBB=LBB+c*P[i]/W[i];
			for(j=i+1;j<=N;j++)
			{

				if(c>=W[j])
				{
					c=c-W[j];
					LBB=LBB+P[j];
				}
			}
			return 0;
		}
			c=c-W[i];
		LBB=LBB+P[i];
	}
	UBB=LBB;
	return 0;
}


NEWNODE(int par,int lev,int t,int cap,int prof,int ub,int mark)
{
	struct node *newnode;
	newnode=(struct node *)malloc(sizeof(struct node));
	newnode->Parent=par;
	newnode->Lever=lev;
	newnode->Tag=t;
	newnode->CU=cap;
	newnode->PE=prof;
	newnode->UB=ub;
	newnode->mark=mark;
	INSERT(newnode);
}

INSERT(struct node *node)
{
	struct node *p,*q;
	p=head;
	if(head==null)
	{
		head=node;
		node->next=null;
	}
	else
	{
		while((p->UB>=node->UB)&&(p->next!=null))
		{
			q=p;
			p=p->next;
		}
		if(p->UB<node->UB)
		{
			if(head==p)
			{
				node->next=head;
				head=node;
			}
			else
			{
				q->next=node;
				node->next=p;
			}

		}
		else
		{
			p->next=node;
			node->next=null;
		}
	}
}


insert(struct node *node)
{
	struct node *p;
	p=newhead;
	if(newhead==null)
	{
		newhead=node;
		node->next=null;
	}
	else
	{
		newhead=node;
		node->next=p;
	}
}

struct node *LARGEST()
{
	struct node *node;
	node=head;
	head=head->next;
	return node;

}


FINISH(int L,int N)
{
	int i,j,m=3;
	int result[4];
    printf("最優解的效益值為:%d\n",L);
	for(j=N;j>=1;j--)
	{
		result[m]=ANS->Tag;
		m--;
		i=ANS->Parent;
		ANS=SEARCH(i);
	}
	printf("最優解選擇是:");
	for(i=0,j=1;i<4;i++,j++)
	{
		if(result[i]==1)
		{
			printf("%d  ",j);
		}
	}
	printf("號物品!\n");

}

struct node *SEARCH(int m)
{
	struct node *p;
	p=newhead;
	while(p!=null)
	{
		if(p->mark==m)
		{
			return p;
		}
		else p=p->next;
	}
	return null;
}



void main()
{
	LCKNAP(15,4,0);
}