Greedy Algorithms
The greedy algorithm follows the problem-solving heuristic of making the locally optimal choice at each stage. A greedy strategy does not always produce an optimal solution. Still, a greedy heuristic may give an optimal solution.
We start by assuming a problem scenario, where we are packing things for a trek; we aim to pack items that are helpful for the hike and also to try to keep our knapsack as light as possible because hiking with lighter luggage is more fun!😛
So, the optimal solution is to carry the most valuable things which are not that heavy.
There are four approaches to this:
1. Being greedy on profit
2. Being greedy on weight
3. Being greedy on Pᵢ/Wᵢ ratio
4. K-optimal greedy heuristic
To proceed further, let’s assume a practical scenario where we are packing things for a trek, and we have four objects {A, B, C, D} with the corresponding weights,
W={20,30,40,70}
And every object has a priority say on a scale of 200,
P={70,80,90,200}
And also maximum capacity of our knapsack is 60.
Greedy on Profit:
In this approach we add the objects into the knapsack based on their priority irrespective of all other factors i.e. The object with highest priority goes into the knapsack first.
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
C = 60
So in our case, the object with the highest priority is ‘D,’ so we try to add D into our sack, but D exceeds the maximum capacity of our sack,
so we try to add the object with the next highest priority, that is object ‘C’ weight of object C is less than maximum capacity, so we add C,
After adding C into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 60–40 = 20
Now we try to add the object with the next highest priority, that is, object ‘B’ weight of object ‘B’ exceeds the remaining capacity, so we search for the object with the next highest priority, which is the object ‘A’
We add A into the sack,
Capacity = 20–20 = 0
So, at the end contents of our knapsack are,
{C, A}
Weight of Knapsack at the end (ΣWᵢ) = 40 + 20 = 60
Profit/Priority Score (ΣPᵢ) = 90 + 70 = 160
Greedy on Weight:
We always try to keep our knapsack as light as possible, because hiking with lighter luggage is more fun!😛
In this approach, we start filling the knapsack with the lowest weight, so the object with the lowest weight goes into the knapsack first, irrespective of all other factors.
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
C = 60
So in our case, the object with the lowest weight is ‘A,’ so we add A into our sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 60–20 = 40
Now we try to add the object with the next lowest weight, that is, object ‘B’ weight of object B is less than maximum capacity, so we add B,
After adding B into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 40–30 = 10
Since there are no more objects lesser than the capacity, we stop adding, and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
Greedy on (Pᵢ/Wᵢ) ratio:
In this version, items can be broken into smaller pieces. So, we may take only a fraction xᵢ of iᵗʰ item.
0⩽xᵢ⩽10⩽xᵢ⩽1
The iᵗʰ item contributes the weight xᵢ.wᵢ to the total weight in the knapsack and profit xᵢ.pᵢ to the total profit.
Hence, the objective of this algorithm is to maximize,
∑(xᵢ.pᵢ)
subject to constraint,
∑(xᵢ.wᵢ)⩽ W
It is clear that an optimal solution must fill the knapsack exactly, otherwise we could add a fraction of one of the remaining items and increase the overall profit.
Thus, an optimal solution can be obtained by
∑(xᵢ.wᵢ)⩽ W
In this context, first we need to sort those items according to the value of Pᵢ/Wᵢ so that,
(Pᵢ+1)/(Wᵢ+1)⩽Pᵢ/Wᵢ
So now we start filling the knapsack with highest (Pᵢ/Wᵢ) ratio so the object with (Pᵢ/Wᵢ) ratio goes into the knapsack first, irresepective of all other factors.
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
C = 60
So now we start filling the knapsack with highest (Pᵢ/Wᵢ) which is ‘A’ so we add ‘A’,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 60–20 = 40
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘D’ , but we cant add ‘D’ because remaining capacity is less than weight of ‘D’
So, the object with next highest Pᵢ/Wᵢ ratio is ‘B’ so we add ‘B’,
After adding B into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 40–30 = 10
Since, there are no more objects lesser than the capacity we stop adding and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
K optimal greedy heuristic:
Here, we place ‘K’ objects into our sack irrespective of everything and add remaining items into the sack in descending order of Pᵢ/Wᵢ ratio.
If object is placed into the sack our vector takes magnitude ‘1’ else ‘0’,
Ex. If object ‘A’ and ‘D’ are put into the sack then our vector is
v = [1,0,0,1]
K takes the integral values ranging between ‘0’ and ’n’ where ’n’ is total number of items.
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Case 1 :
When K = 0, No object is placed first we fill it in descending order of Pᵢ/Wᵢ ratio, which is already done before in this article which yielded the following results,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Case 2 :
When K = 1, We will have four sub-cases,
- Sub-case 1: Placing ‘A’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘B’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘C’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘D’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
Sub-case 1:
We start by adding ‘A’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–20 = 40
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘D’ , but we cant add ‘D’ because remaining capacity is less than weight of ‘D’
So, the object with next highest Pᵢ/Wᵢ ratio is ‘B’ so we add ‘B’,
After adding B into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 40–30 = 10
Since, there are no more objects lesser than the capacity we stop adding and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Sub-case 2:
We start by adding ‘B’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–30 = 30
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘A’ , we add ‘A’ into the sack,
Capacity = 30 - 20 = 10
Since there are no more objects lesser than the capacity, we stop adding, and we end packing,
Now we have,
{B , A} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 30 + 20=50
Profit/Priority Score (ΣPᵢ) = 80 + 70= 150
v = [1,1,0,0]
Sub-case 3:
We start by adding ‘C’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–40 = 20
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘A’ , we add ‘A’ into the sack,
Capacity = 20–20 = 0
Since there are no more space left, we stop adding, and we end packing,
Now we have,
{C , A} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 40 + 20= 60
Profit/Priority Score (ΣPᵢ) = 90 + 70 = 160
v = [1,0,1,0]
Sub-case 4:
We try to add ‘D’ into the sack irrespective of all other factors, but the weight of ‘D’ is more than the sack’s capacity, so we can’t add ‘D.’
So, this sub-case is infeasible to proceed further.
Case 3:
When K = 2, We first place two objects into the sack irrespective of all other factors, and then we try to place the remaining objects in descending order of Pᵢ/Wᵢ ratio,
All the possible sets of two elements are,
(A,A),(A,B),(A,C),(A,D),(B,A),(B,B),(B,C),(B,D),(C,A),(C,B),(C,C),(C,D),(D,A),(D,B),(D,C),(D,D)
Removing the duplicates and the sets who’s weight sum is more than 60, we end up with,
(A,B),(A,C)
Sub-case 1: (A,B)
We start by adding ‘A’ and ‘B’ into the sack irrespective of all other factors,
After adding ‘A’ and ‘B’,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–(20+30) = 10
Since there are no more objects lesser than the capacity, we stop adding, and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Sub-case 2: (A,C)
We start by adding ‘A’ and ‘C’ into the sack irrespective of all other factors,
After adding ‘A’ and ‘C’,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–(20+40) = 0
Since there is no more space left, we stop adding, and we end packing,
Now we have,
{A , C} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 40 + 20= 60
Profit/Priority Score (ΣPᵢ) = 90 + 70 = 160
v = [1,0,1,0]
Case 4:
When, K=3 we must add three objects into the sack irrespective of all other factors, but the sum of any three objects exceeds the sack’s capacity, so we stop here because K cannot take any values greater than or equal to 3.
//Fractional Knapsack Pᵢ/Wᵢ
#include<stdio.h>float p[10],v[10],w[10],t,x[10];int W,n;void sort(){int i,j;for(i=0;i<n;i++)for(j=i+1;j<n;j++){if(p[i]<p[j]){t=p[j];p[j]=p[i];p[i]=t;t=w[j];w[j]=w[i];w[i]=t;t=v[j];v[j]=v[i];v[i]=t;}}}float knapsack(){int i;float total=0;for(i=0;i<=n;i++){if(w[i]>W){x[i]=W/w[i];total=total+p[i]*W;break;}else{x[i]=1;total=total+v[i];W=W-w[i];}}return total;}int main(){int i;float s;printf("Enter the number of items: ");scanf("%d",&n);printf("\nEnter the weights of corresponding items: ");for(i=1;i<=n;i++){scanf("%f",&w[i]);}printf("\nEnter the corresponding profit: ");for(i=1;i<=n;i++){scanf("%f",&v[i]);}printf("\nEnter the maximum weight: ");scanf("%d",&W);for(i=1;i<=n;i++){x[i]=0;p[i]=v[i]/w[i];}sort();s=knapsack();printf("\nTotal cost = %f",s);for(i=1;i<=n;i++)printf("\n%f",x[i]);}// Code by Deepraj Rakshit
