0/1 Knapsack Problem By Greedy Approach

Introduction

 
Hi guys! This article is a continuation of my last article ‘What is Knapsack problem’ so if you don’t read that please follow-through that article first for reading it before. In this article, I am trying to explain how I solved the knapsack problem using the greedy method approach.
 
So, let’s start.
 
As the name suggests, the greedy approach refers to a thief who is very greedy for stolen things. He steals things in a fraction of parts.
 

Method for Solving

  • Arrange all given items in descending order of per weight profit eg. According to Profit/weight
  • Now, start selection from this list, the weight of the item is less than the remaining capacity of the knapsack
Example 1
 
For the given set of items and knapsack capacity = 6 kg, find the optimal solution for the fractional knapsack problem making use of the greedy approach.
or...
 
Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider:
 
n = 4
m = 6 kg
(w1, w2, w3, w4) = (3,2,10,2)
(p1, p2, p3, p4) = (15,20,30,14)
 
Solution
 
Find out profit per weight Pi/Wi
 
Arrange according to Pi/wi

Selection (Xi) Steps

 
Okay, let’s have the capacity m=6
 
The first profitable item we have are item no.2 so we select is 6-2=4 now the remaining knapsack capacity is 4 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .4, so we select 4-2=2 now the remaining knapsack capacity is 2 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .1 and its weight is 3 and our knapsack remaining capacity is 2. Now we are dealing with a greedy approach and select 2/3 items. (like take as we can )
 
So our selection is 2/3.
 
Now we don’t have the remaining capacity so we can’t take the last item no. 3 so it’s selection is 0.
 
Formula
 
 
Had the problem been a 0/1 knapsack problem, knapsack would contain the following items- < 2,4,1 >
 
The knapsack’s Total profit would be 44 units
 
Example 2
 
For the given set of items and knapsack capacity = 15 kg, find the optimal solution for the fractional knapsack problem making use of the greedy approach.
Solution
 
Find out profit per weight Pi/Wi
 
Arrange according to Pi/wi
 

Selection (Xi) Steps

 
Okay,let’s have the capacity m=15
 
The first profitable item we have are item no.5, so we select is 15-1=14. Now the remaining knapsack capacity is 14 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .7 so we select 14-6. Now the remaining knapsack capacity is 8 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .1 so we select 8-2. Now the remaining knapsack capacity is 6 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .3 so we select 6-2. Now the remaining knapsack capacity is 4 and our selection is 1(means selected)
 
Then we have the next profitable item is item no .2. Its weight is 5 and our knapsack remaining capacity is 4, so now we are dealing with a greedy approach and select 4/5 items. (like take as we can )
 
So our selection is 4/5.
 
Now we don’t have any remaining capacity so we can’t take any more items, so it’s selection is made 0 for other items.
 
Formula
 

Conclusion

 
Had the problem been a 0/1 knapsack problem, the knapsack would contain the following items- < 5,7,1,3,2 >.
 
Knapsack’s total profit would be 65 units.
 
Hence, we have solved the 0/1 knapsack problem through the greedy approach.