knap sack algorithm implementation with c

knap sack is very important algorithm. so we tried you provide this to you.

feel free to demand others implementations in comments.

#include<stdio.h>

#include<stdlib.h>

float gcd(float x,int y)


while(y!=0)


if(x>y)

x=x-y;

else

y=y-x;

printf(“retuned %f\n “,x);

return x;


void sort(float *p,float *w,int n,int *t)


int i,j,temp;

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

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


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


temp=t[j];

t[j]=t[i];

t[i]=temp;

temp=p[j];

p[j]=p[i];

p[i]=temp;

temp=w[j];

w[j]=w[i];

w[i]=temp;

int main()


int n,m,i,j;

float p[10],w[10],temp,x[10],price=0,g;

int *t;

printf(“Enter no. of element\n”);

scanf(“%d”,&n);

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

    printf(“Enter the %d element’s price: \n”,i);

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


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

    printf(“the price given for %d element is : %f\n”,i,p[i]);

*/

t=(int *)calloc(n,sizeof(int));

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

    printf(“Enter the %d element’s weight: \n”,i);

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


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

    printf(“the weight given for %d element is : %f\n”,i,w[i]);

*/

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


r[i]=(p[i]/w[i]);

printf(“the ratio  for %d element is : %f \n”,i,r[i]);

*/

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

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


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


temp=p[j];

p[j]=p[i];

p[i]=temp;

temp=w[j];

w[j]=w[i];

w[i]=temp;

*/

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


t[i]=i;

x[i]=0.0;


sort(p,w,n,t);

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

    printf(“the ratio calculated for %d element is : %f\n”,i,r[i]);

*/

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

    printf(“the price given for %d element is : %f\n”,i,p[i]);

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

    printf(“the weight given for %d element is : %f\n”,i,w[i]);

printf(“Enter the capacity(in terms of weight) of the sack:\n”);

scanf(“%d”,&m);

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

    if(w[i]>m)

break;

x[i]=1.0;m=m-w[i];


if(i<=n)

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

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

if(x[i]>0.0)

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

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


printf(“%d \n”,1+t[i]);


*/

printf(“solution vector…\n”);

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


if(x[i]<1.0 && x[i]>0.0)


g=gcd(m,w[i]);

printf(“The element –%d– is consumed X=%d/%d,\n”,(1+t[i]),(m/g),(w[i]/g));

if(x[i]==1.0)

printf(“The element –%d– is consumed X=%f,\n”,(1+t[i]),x[i]);

printf(“Price: %2f\n”,price);

return 0;

knap sack algorithm implementation with c