0
6.5kviews
Solve fractional knapsack problem for the following

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

1 Answer
2
667views

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.

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:

$$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.

Please log in to add an answer.