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-
For each item, compute its value / weight ratio.
Arrange all the items in decreasing order of their value / weight ratio.
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.
- 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-
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.
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)
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?
Compute the value / weight ratio for each item-
Sort all the items in decreasing order of their value / weight ratio-
I1 I2 I5 I4 I3
(6) (4) (3.6) (3.5) (3)
Start filling the knapsack by putting the items into it one by one.
|Knapsack Weight||Items in Knapsack||Cost|
|20||I1, I2, I5||160|
- 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
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.