x

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!

Left-click: follow link, Right-click: select node, Scroll: zoom
x