2017 MAT试题解答(Part XII)

(v) A breakthough can be made by thinking about how to use the conclusion in part (iv). How about if we swap as many items as the condition allows us to?

By thinking in this way, we somehow feel this is quite similar to what we do with a bubble sort! At the end of all the swaps, the items should be arranged in an ascending order in terms of Ti (top to bottom) and the packing is still safe!

We now conclude that any safe packing order can be rearranged to give another safe paking with Ti increasing from top to bottom!

So a practical method is to first calculate the values of Ti for all the items. Then pack from the bottom, with Ti from the greatest to the smallest.

Let’s try with an  example.

Use the packing method.

You can check if it’s a safe packing order!