Write a C Program to perform Fractional Knapsack Problem using Greedy Method.

Description:-

The Greedy algorithm could be understood with a well-known problem known as Knapsack problem. Although the same problem could be solved by employing other algorithmic approaches, Greedy approach solves Fractional Knapsack problem reasonably in a good time. Let us discuss the Knapsack problem.
Given a set of items (n), each with a weight (w) and a value (p), now we have to determine maximum or optimal profit from the given data.

Algorithm:-

// p,w are profit and weight vector, and x is a solution vector
// n,m are total item and size of the knapsack repectively
// arrange all the item in profit ratio such a way that p(i)/w(i) > p(i+1)/w(i+1) 
FOR i = 1 TO n
 x(i) = 0
FOR i = 1 TO n
 CHECK IF w(i) > m THEN
  BREAK
 ELSE
  x(i) = 0
  m = m - w
  c = c + p(i)*x(i)
 END IF
END FOR
CHECK IF i <= n THEN
 x(i) = m/w(i)
 m = 0
 c = c + p(i)*w(i)
END IF

Program:- 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include<stdio.h> // this code is written by Monish Kumar Bairagi struct knap{ int p,w; float r,x; }; void print(knap l[],int n){ int i,j; printf("\n"); for(i=0;i<n;i++) printf("|%d %d %.2f %.2f |",l[i].p,l[i].w,l[i].r,l[i].x); } float knapsack(int n,int m){ int i,j; float profit = 0.0; knap k[10],t; for(i=0;i<n;i++){ printf("Enter Pricr and Weight of Item-%d: ",i+1); scanf("%d%d",&k[i].p,&k[i].w); k[i].r = float(k[i].p)/float(k[i].w); } print(k,n); printf(" ------>( At first the array look like )\n"); for(i=0;i<n-1;i++) for(j=i;j<n;j++){ if(k[i].r < k[j].r ){ t = k[i]; k[i] = k[j]; k[j] = t; } } print(k,n); printf(" ------>( After sorting the array w.r.t R )\n"); for(i=0;i<n;i++){ if(k[i].w < m){ k[i].x = 1; m -= k[i].w; } else{ k[i].x = float(m)/float(k[i].w); m = 0; } profit += float(k[i].p)*k[i].x; } print(k,n); printf(" ------>( Finally the array look like )\n"); return profit; } // this code is written by Monish Kumar Bairagi int main() { int n,m; printf("Enter Total Item: "); scanf("%d",&n); printf("Enter size of Knapsack: "); scanf("%d",&m); printf("\n"); printf("\nMaximum Profit will be %.2f.\n",knapsack(n,m)); return 0; }

 Output:-

Enter Total Item: 4
Enter size of Knapsack: 15

Enter Pricr and Weight of Item-1: 20 8
Enter Pricr and Weight of Item-2: 20 5
Enter Pricr and Weight of Item-3: 12 6
Enter Pricr and Weight of Item-4: 18 6

|20 8 2.50 0.00 ||20 5 4.00 0.00 ||12 6 2.00 0.00 ||18 6 3.00 0.00 | ------>( At first the array look like )

|20 5 4.00 0.00 ||18 6 3.00 0.00 ||20 8 2.50 0.00 ||12 6 2.00 0.00 | ------>( After sorting the array w.r.t R )

|20 5 4.00 1.00 ||18 6 3.00 1.00 ||20 8 2.50 0.50 ||12 6 2.00 0.00 | ------>( Finally the array look like )

Maximum Profit will be 48.00. 

 

Time Complexity:- 

 O(n^2) for all Cases.