bin-packing algorithms
npm install bin-packerPacks objects into bins of a specified capacity.
Repacking algorithms have been moved to bin-repacker.
``bash`
npm install bin-packer
#### Arguments
- obj: The array or object whose own enumerable property values are to be binned (property keys obj
are discarded). Modifies , though not its values, if it is an array, so pass in a shallow sizeOf
copy if you want to preserve the original.
- : A function from items in obj to their numerical sizes. Will be called multiple times capacity
on each item by most algorithms. So if this would be an expensive operation, it is advisable to
supply a function that returns the memoized value.
- : The maximum bin size.
: An array of arrays, each containing elements with total size less than or equal to
capacity.
- oversized: An array containing any elements which on their own have a size greater than
capacity.#### nextFit(obj, sizeOf, capacity)
Opens a new bin whenever a value doesn't fit in the latest one.
#### firstFit(obj, sizeOf, capacity)
Tries to fit new items sequentially in all opened bins before opening a new one.
#### firstFitDecreasing(obj, sizeOf, capacity)
Runs a sort, so the hardest to place items are placed first, then uses First Fit.
#### bestFitDecreasing(obj, sizeOf, capacity)
Sorts items largest to smallest like First Fit Decreasing and then places each one in the fullest
bin into which it will fit. Best Fit Decreasing should generally be preferred to First Fit and
First Fit Decreasing since the Best Fit algorithm uses binary search to find the target bin for
each item rather than First Fit's linear search and is considerably faster.
#### binCompletion(obj, sizeOf, capacity)
Korf's Bin Completion algorithm for producing an optimal solution. Warning! Bin packing is an
NP-hard problem. Time and resource consumption may be high.
$3
Each bound function returns an object with the following keys:
- bound: A lower bound on the number of bins required by an optimal solution.
- oversized: The number of oversized items.#### lowerBound1(obj, sizeOf, capacity)
Simple to compute: the number of bins required if elements' sizes could be split across bins to
fill each completely before opening a new one.
#### lowerBound2(obj, sizeOf, capacity)
Martello and Toth's L2 lower bound on the number of bins required by an optimal solution. Combines
the methodology of the L1 lower bound with the addition of a 'waste' component for each bin that
can be shown not to be fully fillable.
Example
Example JSON input:
`json
[ { "size": 3.08, "label": "dolore" },
{ "size": 7.89, "label": "nulla" },
{ "size": 44.51, "label": "nostrud", "OVERSIZED": "Size is larger than capacity." },
{ "size": 6.62, "label": "proident" },
{ "size": 2.07, "label": "occaecat" },
{ "size": 0.79, "label": "consectetur" },
{ "size": 8.05, "label": "in" },
{ "size": 0.13, "label": "fugiat" },
{ "size": 2.88, "label": "eiusmod" },
{ "size": 5.56, "label": "nisi" }
]
`
Pack it into bins:
js
const binPacker = require('bin-packer')
//, data = JSON.parse(...)
, sizeOf = item => item['size']
, capacity = 10
, result = binPacker.bestFitDecreasing(data.slice(), sizeOf, capacity)console.log("Bins: %O", result.bins)
console.log("Oversized: %O", result.oversized)
`
Results in an array of bins:
js
Bins: [
[
{ size: 7.89, label: 'nulla' },
{ size: 2.07, label: 'occaecat' }
],
[
{ size: 6.62, label: 'proident' },
{ size: 3.08, label: 'dolore' },
{ size: 0.13, label: 'fugiat' }
],
[
{ size: 5.56, label: 'nisi' },
{ size: 2.88, label: 'eiusmod' },
{ size: 0.79, label: 'consectetur' }
],
[ { size: 8.05, label: 'in' } ]
]
Oversized: [
{ size: 44.51, label: 'nostrud', OVERSIZED: 'Size is larger than capacity.' }
]
``