Algorithms (Edexcel A-Level Further Mathematics): Revision Notes

Example 1: First-Fit Algorithm

You have items of sizes $7, 5, 6, 2, 4$ to pack into bins of capacity $10$.

Step 1: Place $7$ in bin 1.

• Bin 1: $[7]$
• Remaining space: $3$

Step 2: Place $5$ in bin 2.

• Bin 2: $[5]$
• Remaining space: $5$

Step 3: Place $6$ in bin 2 (fits in the remaining space).

• Bin 2: $[5,6]$
• Remaining space: $0$

Step 4: Place $2$ in bin $1$(fits in the remaining space).

• Bin 1: $[7,2]$
• Remaining space: $1$

Step 5: Place $4$ in bin 3.

• Bin 3: $[4]$
• Remaining space: $6$

Result:

• Bin 1: $[7, 2]$
• Bin 2: $[5, 6]$
• Bin 3: $[4]$

Example 2: First-Fit Decreasing Algorithm

You have the same items as before: $7, 5, 6, 2, 4$

Step 1: Sort items in decreasing order:

$7, 6, 5, 4, 2$

Step 2: Place $7$ in bin 1.

• Bin 1: $[7]$
• Remaining space: $3$

Step 3: Place $6$ in bin 2.

• Bin 2: $[6]$
• Remaining space: $4$

Step 4: Place $5$ in bin 3.

• Bin 3: $[5]$
• Remaining space: $5$

Step 5: Place $4$ in bin 2.

• Bin 2: $[6,4]$
• Remaining space: $0$

Step 6: Place $2$ in bin 1.

• Bin 1: $[7,2]$
• Remaining space: $1$

Result:

• Bin 1: $[7, 2]$
• Bin 2: $[6, 4]$
• Bin 3: $[5]$

Example 3: Full Bin Packing

You have items of sizes $7, 5, 6, 2, 4$

Step 1: Look for combinations that fill a bin completely:

$6 + 4 = 10$ (Bin 1)

Step 2: Pack remaining items using first-fit:

• Bin 2: $[7, 2]$
• Bin 3: $[5]$

Result:

• Bin 1: $[6, 4]$
• Bin 2: $[7, 2]$
• Bin 3: $[5]$

Common Mistakes

1. Incorrect sorting in FFD: Ensure items are sorted in descending order before applying the first fit.
2. Overlooking exact combinations in full bin packing: Use combinations only when feasible.
3. Confusion about remaining space: Always update the remaining space in bins after placing items.
4. Not testing with multiple methods: Some problems may benefit from comparing the results of different algorithms.
5. Stopping prematurely: Ensure all items are packed.

Key Formulas

1. Bin Packing Goal: Minimise the number of bins such that:

2. First-Fit Steps**:** Place each item into the first bin that has enough space.

3. First-Fit Decreasing Steps: Sort items in descending order, then apply first-fit.

4. Full Bin Packing Steps: Identify exact combinations for full bins, then use another algorithm for the remaining items.