bin-packer

bin-packer

Packs objects into bins of a specified capacity. Repacking algorithms have been moved to bin-repacker.

Install

npm install bin-packer

bin-packer

Methods

Arguments

• obj: The array or object whose own enumerable property values are to be binned (property keys are discarded). Modifies obj, though not its values, if it is an array, so pass in a shallow copy if you want to preserve the original.
• sizeOf: A function from items in obj to their numerical sizes. Will be called multiple times 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.
• capacity: The maximum bin size.

Algorithms

Each algorithm returns an object with the following keys:

• bins: 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.

Bounds

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:

[ { "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:

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:

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.' }
]