- A carpet fitter needs the following lengths, in metres, of carpet.
$$\begin{array} { l l l l l l l l l }
20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25
\end{array}$$
He cuts them from rolls of length 50 m .
- Calculate a lower bound for the number of rolls he needs.
You must make your method clear.
- Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
- Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
- Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.