Solve fractional knapsack problem for the following: n=6, p=(18, 5, 9, 10, 12, 7), w=(7, 2, 3, 5, 3, 2), maximum sack capacity M=13

Fractional Knapsack Problem

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.

Step 2 - Sort all the objects in decreasing order of their Property / Weight Ratio.

Therefore, here sequence of Object as follows:

Step 3 - Start filling the knapsack by putting the object into it one by one.

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:

$$Object\ 5,\ Object\ 6,\ Object\ 3,\ \frac{5} { 7} Object\ 1$$

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 =

$$Profit\ of\ object\ 5 + \ Profit\ of\ object\ 6 + \ Profit\ of\ object\ 3 + \ \frac{5} { 7} \times Profit\ of\ object\ 1$$

$$= 12 + 7 + 9 + \frac 57 \times 18$$

$$=28 + 12.85$$

$$=40.85$$

Total Profit of Knapsack = 40.85

Total Weight of Knapsack =

$$Weight\ of\ object\ 5 + \ Weight\ of\ object\ 6 + \ Weight\ of\ object\ 3 + \ \frac{5} { 7} \times Weight\ of\ object\ 1$$

$$= 3 + 2 + 3 + \frac 57 \times 7$$

$$= 8 + 5$$

$$ = 13$$

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.