PDF chapter test TRY NOW
Let us learn the first-fit decreasing method of packing by considering a situation.
Situation:
A food delivery company delivers food in motorcycles. Each motorcycle can carry a maximum load of \(30 kg\). The parcels that are to be delivered are given below with their weights.
| Food | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) |
| Weight of the food in \(kg\) | \(16\) | \(20\) | \(8\) | \(14\) | \(7\) | \(6\) | \(2\) | \(5\) | \(12\) |
The minimum number of motorcycles required is calculated as follows:
Total weight of the food \(=\) \(16\) \(+\) \(20\) \(+\) \(8\) \(+\) \(14\) \(+\) \(7\) \(+\) \(6\) \(+\) \(2\) \(+\) \(5\) \(+\) \(12\)
\(=\) \(90\)
The maximum load of each motorcycle \(=\) \(30 kg\)
Therefore, the minimum number of motorcycles required \(=\) \(\frac{90}{30}\)
\(=\) \(3\)
Here the minimum requirement of motorcycles may or may not be the answer to this problem. \(3\) motorcycles may or may not be enough to carry all the food items.
First-fit decreasing method:
Step \(1\): Re-order the food parcels in descending order.
| Food | \(2\) | \(1\) | \(4\) | \(9\) | \(3\) | \(5\) | \(6\) | \(8\) | \(7\) |
| Weight of the food in \(kg\) | \(20\) | \(16\) | \(14\) | \(12\) | \(8\) | \(7\) | \(6\) | \(5\) | \(2\) |
Step \(2\): Place each parcel of food items in the first motorcycle and continue trying to fit them in each motorcycle where there is still space for each parcel until all the parcels are placed, as shown in the table below.
| Motorcycle \(1\) | Motorcycle \(2\) | Motorcycle \(3\) | |
| \(20\) \(kg\) | \(16\) \(kg\) | \(12\) \(kg\) | |
| \(8\) \(kg\) | \(14\) \(kg\) | \(7\) \(kg\) | |
| \(2\) \(kg\) | \(6\) \(kg\) | ||
| \(5\) \(kg\) | |||
| Total load in the motorcycle in \(kg\) | \(30\) \(kg\) | \(30\) \(kg\) | \(30\) \(kg\) |
| Remaining load in each motorcycle in \(kg\) | \(0\) \(kg\) | \(0\) \(kg\) | \(0\) \(kg\) |
In the above table, observe the following:
Food \(2\) - \(20\) \(kg\): Place it in the first motorcycle so that the remaining capacity is \(10\) \(kg\).
Food \(1\) - \(16\) \(kg\): Place it in the second motorcycle so that the remaining capacity is \(14\) \(kg\).
Food \(4\) - \(14\) \(kg\): As there is enough space in the second motorcycle, place it in the second motorcycle and the remaining capacity is \(0\) \(kg\).
Food \(9\) - \(12\) \(kg\): Since there is not enough space in the first two motorcycles, place it in the third motorcycle so that the remaining capacity is \(18\) \(kg\).
Food \(3\) - \(8\) \(kg\): As there is enough space in the first motorcycle, place it in the first motorcycle so that the remaining capacity is \(2\) \(kg\).
Food \(5\) - \(7\) \(kg\): As there is enough space in the third motorcycle, place it in the third motorcycle so that the remaining capacity is \(11\) \(kg\).
Food \(6\) - \(6\) \(kg\): As there is enough space in the third motorcycle, place it in the third motorcycle so that the remaining capacity is \(5\) \(kg\).
Food \(8\) - \(5\) \(kg\): As there is enough space in the third motorcycle, place it in the third motorcycle and that the remaining capacity is \(0\) \(kg\).
Food \(7\) - \(2\) \(kg\): As there is enough space in the first motorcycle, place it in the first motorcycle and the remaining capacity is \(0\) \(kg\).
Therefore, using this method, we need \(3\) motorcycles to carry all the food parcels.
Also, there is no remaining space in the motorcycles.
Hence, we can say that the motorcycles are utilized to the optimum level.
Pros and cons of first-fit decreasing method:
- It is an easy method to be followed.
- Usually given a better solution compared to the first-fit method.
Register for free to see more content