Knapsack Problem

#include<stdio.h>

void knapsack(int n,float weight[],float profit[],int capacity)
{
    float x[20],tp=0,u;
    int i,j;
    u=capacity;
    for(i=0;i<=n;i++)
    {
        x[i]=0;
    }
    for(i=0;i<n;i++)
    {
        if(weight[i]>u)
            break;
        else
        {
            x[i]=1;
            tp=tp+profit[i];
            u=u-weight[i];
        }
    }
    if(i<n)
    {
        x[i]=u/weight[i];
        tp=tp+profit[i]*x[i];
    }
    printf("Resultant vector is\n");
    for(i=0;i<n;i++)
        printf("%f ",x[i]);
    printf("\nMaximum profit is %f",tp);
}

void main()
{
    float weight[20],profit[20],ratio[20],temp;
    int num,i,j,capacity;
    printf("Enter the number of objects ");
    scanf("%d",&num);
    printf("Enter profit of each object ");
    for(i=0;i<num;i++)
        scanf("%f",&profit[i]);
    printf("Enter weight of each object ");
    for(i=0;i<num;i++)
        scanf("%f",&weight[i]);
    printf("Enter the capacity of the knapsack ");
    scanf("%d",&capacity);
    for(i=0;i<num;i++)
        ratio[i]=profit[i]/weight[i];
    for(i=0;i<num;i++)
    {
        for(j=0;j<num-i;j++)
        {
            if(ratio[j]<ratio[j+1])
            {
                temp=ratio[j];
                ratio[j]=ratio[j+1];
                ratio[j+1]=temp;

                temp=weight[j];
                weight[j]=weight[j+1];
                weight[j+1]=temp;

                temp=profit[j];
                profit[j]=profit[j+1];
                profit[j+1]=temp;
            }
        }
    }
    printf("\nProfit and weights are\n");
    for(i=0;i<num;i++)
        printf("%f ",profit[i]);
    printf("\n");
    for(i=0;i<num;i++)
        printf("%f ",weight[i]);
    printf("\n");
    knapsack(num,weight,profit,capacity);
}

/*Output
Enter the number of objects 3
Enter profit of each object 25 24 15
Enter weight of each object 18 15 10
Enter the capacity of the knapsack 20

Profit and weights are
24.000000 15.000000 25.000000
15.000000 10.000000 18.000000
Resultant vector is
1.000000 0.500000 0.000000
Maximum profit is 31.500000
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s