First-Fit Decreasing

Sort Decreasing

First-fit decreasing begins by sorting item sizes from largest to smallest.

highlighted = computed this step

Largest first

First-fit decreasing sorts items from largest size to smallest size.

decreasing size order\text{decreasing size order}
First-fit decreasingThe chart shows the sorted order and the bins selected by first fit.first-fit decreasing packingsorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance

Ties stay stable

The two half-size items stay A then B, and the three one-third items stay C then D then E.

A,B,C,D,EA,B,C,D,E
First-fit decreasingThe chart shows the sorted order and the bins selected by first fit.first-fit decreasing packingsorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance

Sorted order

The sorted order is A, B, C, D, E.

order=A,B,C,D,E\text{order}=A,B,C,D,E
First-fit decreasingThe chart shows the sorted order and the bins selected by first fit.first-fit decreasing packingsorted orderA=1/2B=1/2C=1/3D=1/3E=1/3Bin 1A 1/2B 1/2fill 1left 0Bin 2C 1/3D 1/3E 1/3fill 1left 0certificatetotal size2capacity1lower bound2bins used2optimal for this instance