## 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.

Recommended Free Ebook

Similar Articles