The fractional knapsack problem is also one of the techniques which are used to solve the knapsack problem. In fractional knapsack, the items are broken in order to maximize the profit. The problem in which we break the item is known as a Fractional knapsack problem.
This problem can be solved with the help of using two techniques:
- Brute-force approach: The brute-force approach tries all the possible solutions with all the different fractions but it is a time-consuming approach.
- Greedy approach: In Greedy approach, we calculate the ratio of profit/weight, and accordingly, we will select the item. The item with the highest ratio would be selected first.
There are basically three approaches to solve the problem:
- The first approach is to select the item based on the maximum profit.
- The second approach is to select the item based on the minimum weight.
- The third approach is to calculate the ratio of profit/weight.
Consider the below example:
There are various methods are used to solve the Fractional Knapsack Problem such as follows:
- Select the item based on the Maximum Profit.
- Select the item based on the Minimum Weight.
- Calculate the Ratio of Profit/Weight (Greedy Approach).
Here, we used the Ratio of Profit/Weight (Greedy Approach) because it is the best approach among all.
Greedy Approach (Ratio of Profit/Weight)
The given data -
p = (p1, p2, p3, p4, p5, p6) = (18, 5, 9, 10, 12, 7)
w = (w1, w2, w3, w4, w5, w6) = (7, 2, 3, 5, 3, 2)
n = Number of Objects = 6
M = Knapsack Capcacity = 13
Solution -
Step 1 - Calculate the Profit/ Weight Ratio.
| Object | Profit | Weight | Profit / Weight | Ratio |
|---|---|---|---|---|
| 1 | 18 | 7 | (p1 / w1) = 18 / 7 | 2.57 |
| 2 | 5 | 2 | (p2 / w2)= 5 / 2 | 2.5 |
| 3 | 9 | 3 | (p3 / w3)= 9 / 3 | 3 |
| 4 | 10 | 5 | (p4 / w4)= 10 / 5 | 2 |
| 5 | 12 | 3 | (p5 / w5)= 12 / 3 | 4 |
| 6 | 7 | 2 | (p6 / w6)= 7 / 2 | 3.5 |
Step 2 - Sort all the objects in decreasing order of their Property / Weight Ratio.
Therefore, here sequence of Object as follows:
| Object | Ratio | Profit | Weight |
|---|---|---|---|
| 5 | 4 | 12 | 3 |
| 6 | 3.5 | 7 | 2 |
| 3 | 3 | 9 | 3 |
| 1 | 2.57 | 18 | 7 |
| 2 | 2.5 | 5 | 2 |
| 4 | 2 | 10 | 5 |
Step 3 - Start filling the knapsack by putting the object into it one by one.
| Knapsack Weight | Objects in Knapsack | Profit |
|---|---|---|
| 13 | NULL | 0 |
| 13 – 3 = 10 | 5 | 12 |
| 10 – 2 = 8 | 5, 6 | 12 + 7 = 19 |
| 8 – 3 = 5 | 5, 6, 3 | 19 + 9 = 28 |
Now,
- See the next object 1 cannot be chosen because the remaining capacity of the knapsack is less than the weight of object 1.
- The knapsack weight left to be filled is 5 kg but object 1 weight is 7 kg.
- But, in the fractional knapsack problem, even the fraction of any object can be taken.
- Therefore, here knapsack will contain the following objects as follows:
Where,
5 is the remaining capacity of the knapsack.
7 is the weight of object 1.
- Now, the capacity of the Knapsack is equal to the selected objects.
- Hence, no more objects can be selected.
Step 4 - Based on this calculate the Total Profit and Total Weight of the Knapsack.
Total Profit of Knapsack =
Total Profit of Knapsack = 40.85
Total Weight of Knapsack =
Total Weight of Knapsack = 13 (for the selected objects 5, 6, 3, & 1)
This also Proves that the given capacity of the Knapsack is equal to the selected objects.
M = 13 = Total Weight of Knapsack = 13 (for the selected objects 5, 6, 3, & 1)
Therefore, no more objects can be selected.
0 Comments