-
Notifications
You must be signed in to change notification settings - Fork 0
/
NextFitBinPacking.js
55 lines (48 loc) · 1.67 KB
/
NextFitBinPacking.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const Bin = require("./Bin");
const CAPACITY = 20;
/**
* Next Fit (NF) - Bin Packing
*
* At any given time there is only 1 open bin that we check.
* It considers the items in an order defined by a list 'items'.
* If an item fits inside the currently considered bin, the item is placed inside it.
* Otherwise, the current bin is closed, a new bin is opened and the current item is placed inside this new bin.
*
* Time Complexity: O(n) where n = |items|
* Approximation Guarantee: 2*OPT(n) where n = |items|
* @param {Array} items
*/
function nextFitBinPacking(items) {
let bins = [new Bin({ capacity: CAPACITY })];
let didntFitItems = [];
for (let index = 0; index < items.length; index++) {
const item = items[index];
const lastBin = bins[bins.length - 1];
const isExceedCapacity = item > lastBin.capacity;
if (!isExceedCapacity) {
const isFit = item <= lastBin.capacity - lastBin.load;
if (isFit) {
lastBin.addItem(item);
} else {
bins.push(new Bin({ capacity: CAPACITY }));
bins[bins.length - 1].addItem(item);
}
} else {
didntFitItems.push(item);
}
}
return { bins, didntFitItems };
}
// ----------------
// --- Examples ---
// ----------------
var items = [1, 15, 16, 9, 14, 23, 30, 8, 4];
var { bins, didntFitItems } = nextFitBinPacking(items);
console.log("nextFit([%s]) =", items.join(', '));
console.log(bins);
console.log("Didnt Fit Items: ", didntFitItems, '\n');
var items = [10, 11, 3, 5, 2, 19, 14, 9, 3];
var { bins, didntFitItems } = nextFitBinPacking(items);
console.log("nextFit([%s]) =", items.join(', '));
console.log(bins);
console.log("Didnt Fit Items: ", didntFitItems, '\n');