Write a program to solve the fractional knapsack problem.

Name of the experiment:  Write a program to solve the fractional knapsack problem.

Algorithm:

Algorithm  Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)

for i = 1 to n

   do x[i] = 0

weight = 0

for i = 1 to n

   if weight + w[i] ≤ W then 

      x[i] = 1

      weight = weight + w[i]

   else

      x[i] = (W - weight) / w[i]

      weight = W

      break

return x;

Source Code:

#include<stdio.h>

#include<time.h>

#include<conio.h>

void knapsack(float capacity, int n, float weight[], float profit[])

{

            float x[20], totalprofit,y;

            int i,j;

            y=capacity;

            totalprofit=0;

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

                        x[i]=0.0;

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

            {

                        if(weight[i] > y)

                                    break;

                        else

                        {

                                    x[i]=1.0;

                                    totalprofit=totalprofit+profit[i];

                                    y=y-weight[i];

                        }

            }

            if(i < n)

                        x[i]=y/weight[i];

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

            printf("The selected elements are:-\n ");

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

                        if(x[i]==1.0)

            printf("\nProfit is %f with weight %f ", profit[i], weight[i]);

                        else if(x[i] > 0.0)

            printf("\n%f part of Profit %f with weight %f", x[i], profit[i], weight[i]);

            printf("\nTotal profit for %d objects with capacity %f = %f\n\n", n, capacity,totalprofit);

}

int main()

{

            float weight[20],profit[20],ratio[20], t1,t2,t3;

            int n;

            time_t start,stop;

            float capacity;

            int i,j;

            printf("Enter number of objects: ");

            scanf("%d", &n);

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

            scanf("%f", &capacity);

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

            {

                        printf("\nEnter %d(th)  profit: ", (i+1));

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

                        printf("Enter %d(th)  weight: ", (i+1));

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

                        ratio[i]=profit[i]/weight[i];

            }

            start=time(NULL);

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

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

                        {

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

                                    {

                                                t1=ratio[i];

                                                ratio[i]=ratio[j];

                                                ratio[j]=t1;

                                                t2=weight[i];

                                                weight[i]=weight[j];

                                                weight[j]=t2;

                                                t3=profit[i];

                                                profit[i]=profit[j];

                                                profit[j]=t3;

                                    }

                        }

            knapsack(capacity,n,weight,profit);

            stop=time(NULL);

            printf("\nKnapsack = %f\n", difftime(stop,start));

            getch();

            return 0;

}

Sample Input and Output:

OUTPUT:-

Enter number of objects: 5

Enter the capacity of knapsack:10

Enter 1(th)  profit: 9

Enter 1(th)  weight: 6

Enter 2(th)  profit: 15

Enter 2(th)  weight: 3

Enter 3(th)  profit: 20

Enter 3(th)  weight: 2

Enter 4(th)  profit: 8

Enter 4(th)  weight: 4

Enter 5(th)  profit: 10

Enter 5(th)  weight: 3

The selected elements are:-

Profit is 20.000000 with weight 2.000000

Profit is 15.000000 with weight 3.000000

Profit is 10.000000 with weight 3.000000

0.500000 part of Profit 8.000000 with weight 4.000000

Total profit for 5 objects with capacity 10 = 49.000000

Knapsack = 0.000000