First-Fit Decreasing

Second Bin

The remaining three one-third items fill the second bin exactly.

highlighted = computed this step

Open second bin

C cannot fit in the full first bin, so it opens the second bin.

C starts the second bin\text{C starts the second bin}
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

Add D

D fits after C because 1/3 + 1/3 is still within capacity.

1/3+1/3=2/31/3 + 1/3 = 2/3
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

Add E

E also fits, and the three one-third items fill the second bin exactly.

1/3+1/3+1/3=11/3 + 1/3 + 1/3 = 1
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

Two bins

FFD has used two bins: A+B in the first bin, and C+D+E in the second bin.

bins used=2\text{bins used}=2
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