To find Optimal solution for a Knap Sack Problem using Greedy Method

 #include<stdio.h>

#include<conio.h>

main()

{

clrscr();

int n,m,i,u;

int p[20],w[20];

float x[20];

float optimal=0.0;

printf("Enter number of objects:");

scanf("%d",&n);

printf("Enter capacity of KnapSack:");

scanf("%d",&m);

printf("Enter profits in decreasing order of Pi/Wi:");

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

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

printf("Enter Weights in decreasing order of Pi/Wi:");

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

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

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

x[i]=0.0;

u=m;

for(i=1;i<=m;i++)

{

if(w[i]>u)

break;

else

x[i]=1.0;

u=u-w[i];

}

if(i<=n)

x[i]=(float)u/w[i];

printf("The x values are\n");

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

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

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

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

printf("\nOptimal Solution is %f",optimal);

getch();

}

OutPut:

Enter the number of objects: 3

Enter the capacity of Knapscak:20

Enter profits in decreasing order of pi/wi : 16 15 14

Enter weights in decreasing order of pi/wi : 10 10 10

The x-values are :

1.000000 1.000000 0.000000

Optimal Solution is : 31.000000