First-Fit Decreasing

First Bin

First fit puts A and B together because two halves make one full bin.

highlighted = computed this step

Place A

A starts the first bin with size 1/2.

first bin fill=1/2\text{first bin fill}=1/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

Try B

B is tried in the first bin because first-fit checks open bins in order.

first fit checks the first bin first\text{first fit checks the first bin first}
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

A plus B

A plus B fills the first bin exactly: 1/2 + 1/2 = 1.

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

First bin full

The first bin is full, so later items must go somewhere else.

first bin fill=1\text{first bin fill}=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