Fractional Knapsack Problem

#include<conio.h>
#include<stdio.h>
void get();
void show();
void sort();
#define max 10
int i,j, n,y[max],fp=-1,fw;
float unit[max],w[max],p[max],m,U, x[max];

int main()
{
//now calculate the values of x[i] that sould be included in knapsack
get();
sort();
for(i=1;i<=n;i++)
{
x[i]=0.0;
}
U=m;
for(i=1;i<=n;i++)
{
if(w[i]>U)
break;
x[i]=1.0;
U=U-w[i];
}
if(i<=n)
x[i]=U/w[i];
printf("&f",x[i]);

show();
getch();
return 0;
}

//input the values of n , w , p[i] , w[i]
void get()
{
printf("\n Enter total number of items: ");
scanf("%d",&n);
printf("\n Enter the Maximum capacity of the Sack: ");
scanf("%f",&m);
for(i=1;i<=n;i++)
{
printf("\n Enter the weight of the item # %d : ",i);
scanf("%f",&w[i]);
printf("\n Enter the profit of the item # %d : ", i);
scanf("%f", &p[i]);
}
}
//now arrange the values in p[i] and w[i] in dreacreasing order of the ration p[i]/w[i]

void sort()
{
int t,t1;
float t2;
for(i=1;i<=n;i++)
unit[i] = p[i] / w[i];
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
{
if(unit[i]  < unit[j])
{
t2 = unit[i];
unit[i] = unit[j];
unit[j] = t2;

t = p[i];
p[i] = p[j];
p[j] = t;

t1 = w[i];
w[i] = w[j];
w[j] =t1;
}
}
}
}

//now calculate the values of x[i] that sould be included in knapsack
void show()
{
float s=0.0;
printf("\n\tItem\tWeight\t\tCost\t\tUnit Profit\tSelected ");
for(i=1;i<=n;i++)
printf("\n\t%d\t%f\t%f\t%f\t%f",i,w[i],p[i],unit[i],x[i]);
printf("\n\n The Sack now holds following items ");
for(i=1;i<=n;i++)
{
if(x[i]!=0)
{
s += p[i] * x[i];
printf("%d\t",i);
}
}
printf("%f",s);
}

Post a Comment

Previous Post Next Post