Knapsack 0/1

 Knapsack 0/1

#include<stdio.h>

void sort(int n, float p[],float w[],float v[])

{

    int i,j,temp;

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

    {

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

        {

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

            {

                temp=p[j];

                p[j]=p[i];

                p[j]=temp;

                temp=w[j];

                w[j]=w[i];

                w[i]=temp;

               

                temp=v[j];

                v[j]=v[i];

                v[j]=temp;

            }

        }

    }

}

int knapsack(float p[],float v[], float w[], int n, int c)

{

    int i;

     float t;

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

     {

        if(t<c)

        {

            if((t+w[i])>c)

            {

                w[i]=c-t;

                v[i]=w[i]*p[i];

                t=c;

            }

            else{

                t=t+w[i];

            }

        }

        else

        break;

     }

     return i;

}

int main()

{

    float w[50],p[50],v[50],sum_va=0.0, sum_wt=0.0, temp;

    int n=5;

    int cap=60;

    printf("Enter thge weight and value(pft):\n");

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

    {

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

        p[i]=v[i]/w[i];

    }

    sort(n,p,w,v);

    n=knapsack(p,v,w,n,cap);

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

    {

        printf("\n%f",w[i]);

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

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

        sum_va=sum_va+v[i];

        sum_wt=sum_wt+w[i];

    }

    printf("\n\n sum of value: %f",sum_va);

    printf("\n\n total weight :%f",sum_wt);

    return 0;

}