The bin packing problem assigns objects to the fewest fixed-capacity bins without exceeding capacity. It models practical loading and allocation tasks where exhaustive arrangements grow factorially. section 2.3
Six objects in bins of capacity seven
Objects sized 2, 4, 3, 6, 5, and 1 total 21, establishing a lower bound of three bins. First-fit uses four bins, while first-fit decreasing sorts by size and achieves three fully utilized bins. section 2.3
Useful heuristics trade solution quality against speed:
- First-fit places objects in their given order. section 2.3
- First-fit decreasing sorts objects by size before placement. section 2.3
- Largest-first or smallest-first strategies can produce suboptimal or infeasible results, despite faster search. section 2.3
Listing 2.7 Bin packing problem
import numpy
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.colors import rgb2hex
width = 4 #1
height = 8 #1
container = numpy.full((height,width), 0) #1
objects = [[3,1],[3,3],[5,1],[4,2],[3,2]] #2
def fit(container, object, obj_index, rotate=True): #3
obj_w = object[0] #3
obj_h = object[1] #3
for i in range(height - obj_h + 1): C #3
for j in range(width - obj_w + 1): #3
placement = container[i : i + obj_h, j : j + obj_w] #3
if placement.sum() == 0: #3
container[i : i + obj_h, j : j + obj_w] = obj_index #3
return True #3
return fit(container, object[::-1], obj_index, rotate=False) #3
A Python implementation models a container as a NumPy array and tests whether objects fit, including two-dimensional placement. section 2.3
