Program Code in C for Knapsack Problem

Algorithm


Step 1: Sort pi/wi into nonincreasing order.
Step 2: Put the objects into the knapsack according
to the sorted sequence as possible as we can.
e. g.
n = 3, M = 20, (p1, p2, p3) = (25, 24, 15)
(w1, w2, w3) = (18, 15, 10)
Sol: p1/w1 = 25/18 = 1.32
      p2/w2 = 24/15 = 1.6
      p3/w3 = 15/10 = 1.5
Optimal solution: x1 = 0, x2 = 1, x3 = 1/2
total profit = 24 + 7.5 = 31.5

Program In C

#include<conio.h>
#include<stdio.h>
int main()
{ int n,i;
float m,t;
printf("              capacity of knapsack      :   ");
scanf("%f",&m);
  printf("              no of elements            :   ");
  scanf("%d",&n);
  printf("\n                    INPUT DATA \n");
  float profit=0,f[n],r[n],pf[n],p[n],w[n];
  for(i=0;i<n;i++)
  {
   printf("              profit of Element No%d  :  ",i+1);
   scanf("%f",&p[i]);
   printf("              weignt of Element No%d  :  ",i+1);
   scanf("%f",&w[i]);
  }
 
  printf("\n\n");
 
  for( i=0;i<n;i++)
      r[i]=(p[i]/w[i]);
  for( i=0;i<n;i++)
      printf("       profit to weight ratio for %d Element is %f \n",i+1,r[i]) ;
  printf("\n\n");   
  for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
         {if(r[j]>r[i])
             {t=r[j];
              r[j]=r[i];
              r[i]=t;
              t=p[j];
              p[j]=p[i];
              p[i]=t;
               t=w[j];
              w[j]=w[i];
              w[i]=t;    
             }
         }
        
        
        
         for(i=0;i<n;i++)
         { if(w[i]<=m)
             { m-=w[i];
               f[i]=1;
               pf[i]=p[i]*f[i];
               profit+=pf[i];
             }
            
           else if(m<w[i] && m>0)
             {
               pf[i]=(p[i]*m/w[i]);
               profit+=pf[i];
               f[i]=m/w[i];
                m=0;
             } 
           else
           {f[i]=0;
            pf[i]=0;
            } 
         }    
              
   
    printf("       profit given      weight given       fraction taken      profit earned \n\n");
    for(int i=0;i<n;i++)
     printf("       %f            %f         %f            %f       \n",p[i],w[i],f[i],pf[i]);
    
     printf("\n\n\n       TOTAL PROFIT IS : %f",profit);                                                                                             
   getch();  
}