C program to implement knapsack algorithm using greedy approach

Q.Write a C program for knapsack algorithm using greedy approach

Source Code:->

#include<stdio.h>

#include<conio.h>

#include<process.h>

#define max 10

void main()

 {

  int i,j,n;

  float u,sp,sw,size,p[max],wt[max],x[max];

  clrscr();

  printf("READ THE CAPACITY OF KNAPSACK : ");

  scanf("%f",&size);

  printf("ENTER TOTAL NUMBER OF OBJECTS : ");

  scanf("%d",&n);

  for(i=0;i<n;i++)

   {

    printf("Enter profit of object %d : ",i);

    scanf("%f",&p[i]);

   }

  for(i=0;i<n;i++)

  {

    printf("Enter weight of object %d : ",i);

    scanf("%f",&wt[i]);

   }

 for(i=0;i<n;i++)

  {

   printf("\nPROFIT : %f WEIGHT : %f",p[i],wt[i]);

  }

 for(i=0;i<n;i++)

  {

   for(j=0;j<n;j++)

    {

      if((p[i]/wt[i])>(p[j]/wt[j]))

       {

sp=p[j];

sw=wt[j];

p[j]=p[j+1];

wt[j]=wt[j+1];

p[j+1]=sp;

wt[j+1]=sw;

       }

    }

  }

 printf("\n\nAFTER SORT\n");

 for(i=0;i<n;i++)

  {

   printf("\nPROFIT : %f WEIGHT : %f",p[i],wt[i]);

  }

  u=size;

  for(i=0;i<n;i++)

    x[i]=0.0;

 

 for(i=0;i<n;i++)

   {

      if(u==0)

break;

      else

      {

       if(u>wt[i])

{

 x[i]=1.0;

 u=u-wt[i];

}

       else

{

 x[i]=u/wt[i];

 u=0;

}

      }

   }

 sp=0.0;sw=0.0;

 for(i=0;i<n;i++)

  {

   sp=sp+x[i]*p[i];

   sw=sw+x[i]*wt[i];

  }

 printf("\n\nWEIGHT PER OBJECT\n");

  for(i=0;i<n;i++)

    printf("\nX[%d] = %f",i,x[i]);

 printf("\n\nTOTAL WEIGHT : %f",sw);

 printf("\nTOTAL PROFIT : %f",sp);

 getch();

}

Output:->

READ THE CAPACITY OF KNAPSACK : 20

ENTER TOTAL NUMBER OF OBJECTS : 3

Enter profit of object 0 : 25

Enter profit of object 1 : 24

Enter profit of object 2 : 15

Enter weight of object 0 : 18

Enter weight of object 1 : 15

Enter weight of object 2 : 10

PROFIT : 25.000000 WEIGHT : 18.000000

PROFIT : 24.000000 WEIGHT : 15.000000

PROFIT : 15.000000 WEIGHT : 10.000000

AFTER SORT

PROFIT : 24.000000 WEIGHT : 15.000000

PROFIT : 15.000000 WEIGHT : 10.000000

PROFIT : 25.000000 WEIGHT : 18.000000

WEIGHT PER OBJECT

X[0] = 1.000000

X[1] = 0.500000

X[2] = 0.000000

TOTAL WEIGHT : 20.000000

Share on Google Plus