First-Fit Decreasing Bin Packing

4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to \(30000 \mathrm {~cm} ^ { 3 }\) in volume. The number of each item to be packed, their dimensions and weights are given in the table below. Jill tries to pack the items by weight using the first-fit decreasing method.

1. List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible. Jack tries to pack the items by volume using the first-fit decreasing method.
2. List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
3. Give another reason why a packing may not be possible.

1

1. 1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
   2. Find a packing that uses fewer bags.
2. The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$

1. Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
2. Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
3. Find a way to pack the boxes into the van so that she makes as few deliveries as possible.

1. The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.

$$\begin{array} { l l l l l l l l l l l l } 6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8 \end{array}$$

1. Considering only the total amount, what is the least number of rolls that are needed?
2. Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.
3. Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).
4. Comment on this result.
   

3. \(\begin{array} { l l l l l l l l l l l } 1.8 & 1.4 & 2.6 & 1.6 & 2.8 & 0.9 & 3.1 & 0.8 & 1.2 & 2.4 & 0.6 \end{array}\) \section*{Question 3 continued} \section*{Question 3 continued} \section*{Question 3 continued}

5. Nine pieces of wood are required to build a small cabinet. The lengths, in cm, of the pieces of wood are listed below. $$20 , \quad 20 , \quad 20 , \quad 35 , \quad 40 , \quad 50 , \quad 60 , \quad 70 , \quad 75$$ Planks, one metre in length, can be purchased at a cost of \(\pounds 3\) each.

1. The first fit decreasing algorithm is used to determine how many of these planks are to be purchased to make this cabinet. Find the total cost and the amount of wood wasted.
   (5) Planks of wood can also be bought in 1.5 m lengths, at a cost of \(\pounds 4\) each. The cabinet can be built using a mixture of 1 m and 1.5 m planks.
2. Find the minimum cost of making this cabinet. Justify your answer.
   (4)

The masses, in kg, of ten bags are given below. 8 \quad 10 \quad 10 \quad 12 \quad 12 \quad 12 \quad 13 \quad 15 \quad 18 \quad 18

1. Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. [3]

Only two crates are available, so only some of the bags will be packed. Each bag is given a value.

Bag	A	B	C	D	E	F	G	H	I	J
Mass (kg)	8	10	10	12	12	12	13	15	18	18
Value	6	3	3	2	4	5	4	6	4	4

1. Find a packing into two crates so that the total value of the bags in the crates is at least 32. [3]