Consider that you are going on a field trip in your school and you have six groups of students of group sizes as given below.
You need to fit the group of students in a cab that has a capacity of seven members. How many cabs would you need to arrange so that each group stays together? (Condition: minimum number of cabs to be used & another thing is each group of students stays together, Use First-fit decreasing method:)
Consider that you are going on a field trip in your school and you have six groups of students of group sizes as given below.
You need to fit the group of students in a cab that has a capacity of seven members. How many cabs would you need to arrange so that each group stays together? (Condition: minimum number of cabs to be used & another thing is each group of students stays together, Use First-fit decreasing method:)
The correct option is B 3
the total number of students = 3+1+6+4+5+2 = 21
Capacity of seater of a cab = 7
Therefore, the cab minimum required = 21÷ 7 = 3 cabs.
Now, we don’t know whether 3 cabs can be an answer to this problem. 3 cabs may or may not be enough to accommodate when the group of students stays together.
First-fi t decreasing method:
Step 1. Re-order the group of students so that they are in descending order.
Step 2. Do the same process of the first fi t method to the re-ordered group. Place each group of students in the first cab and continue trying to fi t them in the cabs where there is still space and all are placed as shown in the picture below.
From the above picture, we observe that:
Group 3 – 6 students - accommodate them into 1st cab so that the remaining seat is 1.
Group 6 – 5 students - As there are no enough seats in the 1st cab and so accommodate them into 2nd cab and the remaining seats are 2.
Group 4 – 4 students - As there are no enough seats in the first 2 cabs and so accommodate them into 3rd cab and the remaining seats are 3.
Group 1 – 3 students - Since there enough seats in the 3rd cab, accommodate them into 3rd cab and the remaining seat is 0.
Group 5 – 2 students - Since there are enough seats in the 2nd cab, accommodate them into 2nd cab and the remaining seat is 0.
Group 2 – 1 student - Since there is a seat left in the 1st cab, accommodate him into 1st cab and the remaining seat is 0.
Using this First- fit decreasing method, we need 3 cabs and there are no remaining seats and hence seats are used to the optimum level.
the total number of students = 3+1+6+4+5+2 = 21
Capacity of seater of a cab = 7
Therefore, the cab minimum required = 21÷ 7 = 3 cabs.
Now, we don’t know whether 3 cabs can be an answer to this problem. 3 cabs may or may not be enough to accommodate when the group of students stays together.
First-fi t decreasing method:
Step 1. Re-order the group of students so that they are in descending order.
Step 2. Do the same process of the first fi t method to the re-ordered group. Place each group of students in the first cab and continue trying to fi t them in the cabs where there is still space and all are placed as shown in the picture below.
From the above picture, we observe that:
Group 3 – 6 students - accommodate them into 1st cab so that the remaining seat is 1.
Group 6 – 5 students - As there are no enough seats in the 1st cab and so accommodate them into 2nd cab and the remaining seats are 2.
Group 4 – 4 students - As there are no enough seats in the first 2 cabs and so accommodate them into 3rd cab and the remaining seats are 3.
Group 1 – 3 students - Since there enough seats in the 3rd cab, accommodate them into 3rd cab and the remaining seat is 0.
Group 5 – 2 students - Since there are enough seats in the 2nd cab, accommodate them into 2nd cab and the remaining seat is 0.
Group 2 – 1 student - Since there is a seat left in the 1st cab, accommodate him into 1st cab and the remaining seat is 0.
Using this First- fit decreasing method, we need 3 cabs and there are no remaining seats and hence seats are used to the optimum level.
