Knapsack Using Greedy Algorithm In C Programming

# include< stdio.h>
# include< conio.h>


void knapsack(int n, float weight[], float value[], float W)
{
 float x[20], tp= 0;
 int i, j, u;
 u=W;

 for (i=0;i< n;i++)
  x[i]=0.0;

 for (i=0;i< n;i++)
 {
  if(weight[i]>u)
   break;
  else
  {
   x[i]=1.0;
   tp= tp+value[i];
   u=u-weight[i];
  }
 }
 if(i< n)
       x[i]=u/weight[i];

  tp= tp + (x[i]*value[i]);
  printf("\n------------------------------------------------");
  printf("\nweight | ");
  for(i=0;i< n;i++)
  {
   printf("%1.2f\t",weight[i]);
  }
  printf("\nvalue  | ");
 
for(i=0;i< n;i++)
  {
   printf("%1.2f\t",value[i]);
  }
  printf("\n   x   | ");
  for(i=0;i< n;i++)
  {
   printf("%1.2f\t",x[i]);
  }

  printf("\n------------------------------------------------");
  printf("\n Maximum value that knapsack carry is:%.2f", tp);
  printf("\n------------------------------------------------");

}

void main()
{
 float weight[20], value[20], W;
 int n, i ,j;
 float ratio[20], temp;
 clrscr();
 printf("\n------------------------------------------------");
 printf("\n       KNAPSACK PROBLEM USING GREEDY APPROACH    ");
 printf("\n------------------------------------------------");
 
 printf ("\n Enter number of Objects you want:");
 scanf ("%d", &n);

 printf ("\n------Enter the weights and values of each object--------");
 for (i=0; i< n; i++)
 {
  printf ("\nEnter weight and value for object%d:",i+1);
  scanf("%f %f", &weight[i], &value[i]);
 }

 printf ("\nEnter the capacity of knapsack:");
 scanf ("%f", &W);


 for (i=0; i< n; i++)
 {
  ratio[i]=value[i]/weight[i];
 }

 for(i=0; i< n; i++)
 {
  for(j=i+1;j<  n; j++)
  {
   if(ratio[i]< ratio[j])
   {
    temp= ratio[j];
    ratio[j]= ratio[i];
    ratio[i]= temp;

    temp= weight[j];
    weight[j]= weight[i];
    weight[i]= temp;

    temp= value[j];
    value[j]= value[i];
    value[i]= temp;
   }
  }
 }

 knapsack(n, weight, value, W);
 getch();
}


OUTPUT




------------------------------------------------------------------------------------
       KNAPSACK PROBLEM USING GREEDY APPROACH
------------------------------------------------------------------------------------
 Enter number of Objects you want:5

----------------Enter the weights and values of each object--------------
Enter weight and value for object1:10 20

Enter weight and value for object2:20 30

Enter weight and value for object3:30 66

Enter weight and value for object4:40 40

Enter weight and value for object5:50 60

Enter the capacity of knapsack:100

------------------------------------------------------------------------------------
weight | 30.00  10.00   20.00   50.00   40.00
value  | 66.00  20.00   30.00   60.00   40.00
  x    |  1.00   1.00    1.00    0.80    0.00
------------------------------------------------------------------------------------
 Maximum value that knapsack carry is:164.00
------------------------------------------------------------------------------------