1D bin packing "First Fit (Decreasing)" algorithm

Usage

bin_pack_ffd(x, cap, sort = TRUE)

Arguments

x: A numeric vector of item sizes to be fit into bins. Each value represents the size of an atomic item. If a value is NA it is ignored and the corresponding result will also be NA.
cap: Bin capacity in units of values in x. A scalar value. If an individual item size is above cap a single bin is reserved for this item.
sort: Determines whether the input vector should be sorted in decreasing order before applying the "First Fit" algorithm ("First Fit Decreasing").

Value

A integer vector of labels of the same length as x. The integer label at position i determines the assignment of the ith item with size x[i] to a bin. If the value x[i] is NA the result label at position i will also be NA.

Details

See Wikipedia for a concise introduction or "The Art of Computer Programming Vol. 1" by Donald E. Knuth (1997, ISBN: 0201896834) for more details.

Examples

# Generate a vector of item sizes
x <- sample(100, 1000, replace = TRUE)

# Pack those items into bins of capacity 130
bins <- bin_pack_ffd(x, cap = 130)

# Number of bins needed to pack the items
print(length(unique(bins)))
#> [1] 393