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.