Fractional Knapsack Problem | Greedy Method | Example

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-

1. Fractional Knapsack Problem
2. 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,

Watch this Video Lecture

 

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.