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

Monish Bairagi April 13, 2020

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.
Tags
Reactions
Monish Bairagi

Posted by Monish Bairagi

Learner

Post a Comment

0 Comments