**Knapsack Problem-**

You are given the following-

- A knapsack (kind of shoulder bag) with limited weight capacity.
- Few items each having some weight and value.

**The problem states-**

Which items should be placed into the knapsack such that-

- The value or profit obtained by putting the items into the knapsack is maximum.
- And the weight limit of the knapsack does not exceed.

**Knapsack Problem Variants-**

Knapsack problem has the following two variants-

- Fractional Knapsack Problem
- 0/1 Knapsack Problem

In this article, we will discuss about Fractional Knapsack Problem.

**Fractional Knapsack Problem-**

In Fractional Knapsack Problem,

- As the name suggests, items are divisible here.
- We can even put the fraction of any item into the knapsack if taking the complete item is not possible.
- It is solved using Greedy Method.

**Also Read-****0/1 Knapsack Problem**

**Fractional Knapsack Problem Using Greedy Method-**

Fractional knapsack problem is solved using greedy method in the following steps-

**Step-01:**

For each item, compute its value / weight ratio.

**Step-02:**

Arrange all the items in decreasing order of their value / weight ratio.

**Step-03:**

Start putting the items into the knapsack beginning from the item with the highest ratio.

Put as many items as you can into the knapsack.

**Time Complexity-**

- The main time taking step is the sorting of all items in decreasing order of their value / weight ratio.
- If the items are already arranged in the required order, then while loop takes O(n) time.
- The average time complexity of
**Quick Sort**is O(nlogn). - Therefore, total time taken including the sort is O(nlogn).

**PRACTICE PROBLEM BASED ON FRACTIONAL KNAPSACK PROBLEM-**

**Problem-**

For the given set of items and knapsack capacity = 60 kg, find the optimal solution for the fractional knapsack problem making use of greedy approach.

Item | Weight | Value |

1 | 5 | 30 |

2 | 10 | 40 |

3 | 15 | 45 |

4 | 22 | 77 |

5 | 25 | 90 |

**OR**

Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider-

n = 5

w = 60 kg

(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)

(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)

**OR**

A thief enters a house for robbing it. He can carry a maximal weight of 60 kg into his bag. There are 5 items in the house with the following weights and values. What items should thief take if he can even take the fraction of any item with him?

Item | Weight | Value |

1 | 5 | 30 |

2 | 10 | 40 |

3 | 15 | 45 |

4 | 22 | 77 |

5 | 25 | 90 |

**Solution-**

**Step-01:**

Compute the value / weight ratio for each item-

Items | Weight | Value | Ratio |

1 | 5 | 30 | 6 |

2 | 10 | 40 | 4 |

3 | 15 | 45 | 3 |

4 | 22 | 77 | 3.5 |

5 | 25 | 90 | 3.6 |

**Step-02:**

Sort all the items in decreasing order of their value / weight ratio-

**I1 I2 I5 I4 I3**

(6) (4) (3.6) (3.5) (3)

**Step-03:**

Start filling the knapsack by putting the items into it one by one.

Knapsack Weight | Items in Knapsack | Cost |

60 | Ø | 0 |

55 | I1 | 30 |

45 | I1, I2 | 70 |

20 | I1, I2, I5 | 160 |

Now,

- Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg.
- Since in fractional knapsack problem, even the fraction of any item can be taken.
- So, knapsack will contain the following items-

**< I1 , I2 , I5 , (20/22) I4 >**

Total cost of the knapsack

= 160 + (20/27) x 77

= 160 + 70

= 230 units

**Important Note-**

Had the problem been a 0/1 knapsack problem, knapsack would contain the following items-

**< I1 , I2 , I5 >**

The knapsack’s total cost would be 160 units.

To gain better understanding about Fractional Knapsack Problem,

**Next Article-****Job Sequencing With Deadlines**

Get more notes and other study material of **Design and Analysis of Algorithms**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.