Items and Capacity

Bin Capacity

A bin is feasible when its exact fill stays within capacity.

highlighted = computed this step

Capacity one

Each bin can hold total size 1.

capacity=1\text{capacity}=1
Pinned FFD packingThe grid recomputes the sorted order, bin fills, and lower-bound certificate.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

No overfill

A bin is feasible only when its fill is at most capacity.

fill≤capacity\text{fill}\le \text{capacity}
Pinned FFD packingThe grid recomputes the sorted order, bin fills, and lower-bound certificate.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

Goal

The goal is to use as few bins as possible.

min⁡ number of bins\min \text{ number of bins}
Pinned FFD packingThe grid recomputes the sorted order, bin fills, and lower-bound certificate.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

Visual rule

A full bar means the bin fill is exactly capacity, not just visually close.

full bar means fill=1\text{full bar means fill}=1
Pinned FFD packingThe grid recomputes the sorted order, bin fills, and lower-bound certificate.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