Problem

The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg.

$16 \quad 23 \quad 18 \quad 9 \quad 4 \quad 20 \quad 35 \quad 5 \quad 17 \quad 13 \quad 6 \quad 11$

(a) Calculate a lower bound for the number of containers needed. You must make your method clear.

(b) Use the first-fit bin packing algorithm to allocate the parcels to the containers.

(c) Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.

(d) Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.