Bin-packing Algorithms
First Fit Algorithm
First Fit Algorithm
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
L1 3, 1518 , 220 , 525 , 530
L2 14, 822 , 426 , 329
L3 11, 1728
7 cannot get on, as the amount of space left is less than 7
First Fit Decreasing
First Fit Decreasing
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
L1 17, 1128 , 230
L2 15, 1429
L3 8, 715 , 520 , 525 , 429
Better by 1, two 3m vehicles dont get in
Full Bin Algorithm
Inspection (Full bin algorithm)
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!