The Greedy algorithm could be understood very well with a well-known problem referred to as Knapsack problem. Although the same problem could be solved by employing other algorithmic approaches, Greedy approach solves Fractional Knapsack problem reasonably in a good time. Let us discuss the Knapsack problem in detail.
Knapsack Problem
Given a set of items, each with a weight and a value, determine a subset of items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
The knapsack problem is in combinatorial optimization problem. It appears as a subproblem in many, more complex mathematical models of real-world problems. One general approach to difficult problems is to identify the most restrictive constraint, ignore the others, solve a knapsack problem, and somehow adjust the solution to satisfy the ignored constraints
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.
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
0 Comments