Bin-packing Algorithms

There are 12 vehicles waiting to get on a 3 lane ferry of 30m length
3, 15, 14, 2, 5, 5, 8, 11, 4, 17, 7, 3 m in length respectively
L₁ 3, 15₁₈ , 2₂₀ , 5₂₅ , 5₃₀
L₂ 14, 8₂₂ , 4₂₆ , 3₂₉
L₃ 11, 17₂₈

7 cannot get on, as the amount of space left is less than 7

Sort the list into size order decreasing.
3, 15, 14, 2, 5, 5, 8, 11, 4, 17, 7, 3

17, 15, 14, 11, 8, 7, 5, 5, 4, 3, 3, 2

L₁ 17, 11₂₈ , 2₃₀
L₂ 15, 14₂₉
L₃ 8, 7₁₅ , 5₂₀ , 5₂₅ , 4₂₉

Better by 1, two 3m vehicles dont get in

Can you do any better by yourself?

14+11+5 = 30
15+7+3+5 = 30
17+8+3+2 = 30

4m vehicle left over

\(\therefore\) we can do better!