Post

# 0/1 Knapsack Problem By Greedy Approach

## Introduction

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  