| Title: | Fast 1d Bin Packing |
|---|---|
| Description: | Implements the First Fit Decreasing algorithm to achieve one dimensional heuristic bin packing. Runtime is of order O(n log(n)) where n is the number of items to pack. See "The Art of Computer Programming Vol. 1" by Donald E. Knuth (1997, ISBN: 0201896834) for more details. |
| Authors: | Lukas Schneiderbauer [aut, cre, cph] |
| Maintainer: | Lukas Schneiderbauer <[email protected]> |
| License: | GPL (>= 3) |
| Version: | 0.1.1.9000 |
| Built: | 2024-11-04 04:18:25 UTC |
| Source: | https://github.com/lschneiderbauer/binpackr |
1D bin packing "First Fit (Decreasing)" algorithm
bin_pack_ffd(x, cap, sort = TRUE)bin_pack_ffd(x, cap, sort = TRUE)
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 |
cap |
Bin capacity in units of values in |
sort |
Determines whether the input vector should be sorted in decreasing order before applying the "First Fit" algorithm ("First Fit Decreasing"). |
See Wikipedia for a concise introduction or "The Art of Computer Programming Vol. 1" by Donald E. Knuth (1997, ISBN: 0201896834) for more details.
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.
# 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)))# 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)))