C Program to implement Knapsack Problem using Greedy Method

 

/* Knapsack Problem using Greedy Method */


#include<stdio.h>

#include<conio.h>


void Knapsack(int n, float w[], float p[], float m);

void LargestProfit(int n, float w[], float p[], float m);

void SmallestWeight(int n, float w[], float p[], float m);



int main()

{

 float w[20], p[20], ratio[20], m;

 int n; //p-profit, w-weights, x-ratio, m-capacity, n-num

 int i, j;

 float temp;

 clrscr();



 printf("\nEnter the number of objects: ");

 scanf("%d", &n);

 printf("\nEnter the details: ");

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

 {

  printf("\nItem %d:", i+1);

  printf("\n\tWeight: ");

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

  printf("\tProfit: ");

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

 }

 printf("\nEnter the capacity of Knapsack: ");

 scanf("%f", &m);



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

 {

  ratio[i]=p[i]/w[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 = w[j];

    w[j] = w[i];

    w[i] = temp;



    temp = p[j];

    p[j] = p[i];

    p[i] = temp;

   }

  }

 }

 printf("\nLargest Ratio of Profit by Weight Strategy:\n");

 Knapsack(n, w, p, m);


 printf("\n\nLargest Profit Strategy:\n");

 LargestProfit(n, w, p, m);


 printf("\n\nSmallest Weight Strategy:\n");

 SmallestWeight(n, w, p, m);


 getch();

 return 0;
}



//-------CALCULATE FRACTION OF WEIGHTS AND PROFIT-------

void Knapsack(int n, float w[], float p[], float m)

{

 float x[20], profit;

 int i, j;

 float u;

 u=m;

 profit=0.0;



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

  x[i]=0.0;



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

 {

  if(w[i] > u)

   break;

  else

  {

   x[i]=1.0;

   u=u-w[i];

   profit=profit+p[i];

  }

 }

 if(i<n)

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

 profit=profit + ( x[i] * p[i] );



 printf("\n\tThe resultant vector is ");

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

  printf("%.2f\t", x[i]);



 printf("\n\n\tThe total profit is %.3f", profit);



}



//-------LARGEST PROFIT STRATEGY-------

void LargestProfit(int n, float w[], float p[], float m)

{

 int i, j;

 float temp;

 float ratio[20];



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

 {

  for(j=i+1;j<n;j++)

  {

   if(p[i] < p[j])

   {

    temp = ratio[j];

    ratio[j] = ratio[i];

    ratio[i] = temp;


    temp = w[j];

    w[j] = w[i];

    w[i] = temp;


    temp = p[j];

    p[j] = p[i];

    p[i] = temp;

   }

  }

 }



 Knapsack(n, w, p, m);

}



//-------SMALLEST WEIGHT STRATEGY-------

void SmallestWeight(int n, float w[], float p[], float m)

{

 int i, j;

 float temp;

 float ratio[20];


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

 {

  for(j=i+1;j<n;j++)

  {

   if(w[i] > w[j])

   {

    temp = ratio[j];

    ratio[j] = ratio[i];

    ratio[i] = temp;


    temp = w[j];

    w[j] = w[i];

    w[i] = temp;


    temp = p[j];

    p[j] = p[i];

    p[i] = temp;

   }

  }

 }



 Knapsack(n, w, p, m);

}



/* OUTPUT


Enter the number of objects: 3


Enter the details:

Item 1:

 Weight: 18

 Profit: 25


Item 2:

 Weight: 10

 Profit: 24


Item 3:

 Weight: 10

 Profit: 15


Enter the capacity of Knapsack: 20


Largest Ratio of Profit by Weight Strategy:


 The resultant vector is 1.00    0.50    0.00

 The total profit is 31.500


Largest Profit Strategy:


 The resultant vector is 1.00    0.13    0.00

 The total profit is 28.200


Smallest Weight Strategy:


 The resultant vector is 1.00    0.67    0.00

 The total profit is 31.000

*/