#include <stdio.h>
#define len sizeof(struct node)
typedef struct node{
float bound;
int staus[50];
struct node *next;
}node;
int item[50],wl,n,state[50];
float value[50],weight[50],max_value,ratio[50];
void dele(node *father,node *current){
if(current->next==NULL)
{father->next=NULL;
return;
}
father->next=current->next;
}
void init(node *father,node *son){
int i;
father->next=son;
for(i=0;i<n;i++)
son->staus[i]=0;
son->next=NULL;
}
void branch(){
int i,t,j;
float diff,sum=0,sum_value=0;
node *head,*sonbrother,*father,*son,*prenode,*p,*q;
head=prenode=(node *)malloc(len);
father=(node *)malloc(len);
init(prenode,father);
father->bound=32768;
while(head->next!=NULL)
{
/*1*/ son=(node *)malloc(len);
init(father,son);
for(i=0;i<n&&father->staus[i]!=0;i++)
son->staus[i]=father->staus[i];
t=i;
son->staus[t]=-(t+1);
sum=0;
sum_value=0;
for(j=0;j<t+1&&son->staus[j]!=0;j++)
if(son->staus[j]>0)
{sum=sum+weight[item[j]];
sum_value=sum_value+value[item[j]];
}
while(sum!=wl&&son->staus[n-1]==0)
{diff=wl-(sum+weight[item[j]]);
if(diff>=0)
{sum=sum+weight[item[j]];
sum_value=sum_value+value[item[j]];
}
else
{sum=wl;
sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];
}
j++;
}
son->bound=sum_value;
/*2*/ sonbrother=(node *)malloc(len);
init(son,sonbrother);
for(i=0;i<t;i++)
sonbrother->staus[i]=father->staus[i];
sonbrother->staus[t]=t+1;
sum=0;
sum_value=0;
for(j=0;j<t+1&&sonbrother->staus[j]!=0;j++)
if(sonbrother->staus[j]>0)
{sum=sum+weight[item[j]];
sum_value=sum_value+value[item[j]];
}
if(sum>wl)
{sonbrother->bound=-32768;
dele(son,sonbrother);
}
else
{while(sum!=wl&&sonbrother->staus[n-1]==0)
{diff=wl-(sum+weight[item[j]]);
if(diff>=0)
{sum=sum+weight[item[j]];
sum_value=sum_value+value[item[j]];
}
else
{sum=wl;
sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];
}
j++;
}
sonbrother->bound=sum_value;
}
dele(prenode,father);
father=prenode->next;
if(son->staus[n-1]!=0)
{if(son->next!=NULL)
{max_value=sonbrother->bound;
for(i=0;i<n;i++)
state[i]=sonbrother->staus[i];
dele(son,sonbrother);
dele(prenode,father);
father=prenode->next;
}
else
{max_value=son->bound;
for(i=0;i<n;i++)
state[i]=son->staus[i];
dele(prenode,father);
}
q=head;
p=head->next;
while((p!=NULL)&&(p->bound<=max_value))
{dele(q,p);
p=q->next;
}
if(p!=NULL)
{prenode=q;
father=p;
}
else
return;
}
else
if(father->next!=NULL)
{prenode=prenode->next;
father=father->next;
}
}
return;
}
int getmin(){
int i;
float amin=weight[0];
for(i=1;i<n;i++)
if(amin>weight[i])
amin=weight[i];
return amin;
}
void sort(){
int i,j,exchange=1;
float temp1,temp2;
for(i=0;i<n;i++)
ratio[i]=value[i]/weight[i];
for(j=n-1;j>=0&&exchange==1;j--)
{exchange=0;
for(i=0;i<j;i++)
if(ratio[i+1]>ratio[i])
{exchange=1;
temp1=ratio[i+1];ratio[i+1]=ratio[i];ratio[i]=temp1;
temp2=item[i+1];item[i+1]=item[i];item[i]=temp2;
}
}
}
void main(){
int i,j;
float sum=0;
clrscr();
printf("\tWelcome to the BRANCH_BOUND system!\n");
printf("number of the materials=? ");
scanf("%d",&n);
printf("maximun weigh of the problem=? ");
scanf("%d",&wl);
for(i=0;i<n;i++)
{item[i]=i;
printf("\n*******************\n");
printf("input item%d data!\n",i+1);
printf("*******************\n");
printf("weight %d=? ",i+1);
scanf("%f",&weight[i]);
printf("value %d=? ",i+1);
scanf("%f",&value[i]);
}
if((getmin())>wl)
{printf("\nThere is no solution of the problem!");
exit(0);
}
for(i=0;i<n;i++)
sum=sum+weight[i];
if(sum<=wl)
{printf("\nAll the materials can be loaded!");
exit(0);
}
sort();
branch();
printf("\n\n\nThe maximum value of the materials is %f ",max_value);
printf("\nincluding the following materials\n");
sum=0;
for(i=0;i<n;i++)
if(state[i]>0)
{sum=sum+weight[item[i]];
printf("%d\n",item[i]+1);
}
printf("\nThe weight of the materials is %f ",sum);
getch();
}
