bin_pack_ffd {binpackr}

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

Description

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.

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").

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.

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.

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)))