I’m no math wiz, and I know solutions for these bin packing problems can become pretty complex. However, randomizing the input works pretty efficiently in this case.

So, randomize the initial array, then do a linear grouping of the array based on the lower and upper ranges, checking if the bin is valid afterwards.

Here, I have an array with 50 initial values. I allow it to try up to 10000 attempts, but it usually finds a valid bin within the first 500 tries with the given constraints (min: 2.2, max: 4.2). Many times it is much quicker.

After testing multiple times, I haven’t had a single negative result:

``````const testArr = [1, .5, .4, 1.2, 3, 1.3, 3, .8, .9, 1.2,
2.8, 2.1, .7, .3, .7, 1.8, 1.1, .9, .4, 1.2, 1,
2, 1.1, 1.3, .9, 1.8, 1.7, 1.1, 1.3, 2.8, 2.6, 1.4,
2.9, 2.6, 1.1, .5, .2, 1.8, 2.5, 3.4, 2, 2, 2, 4, 3.1,
1.3, 3, 3, 3.5, 2.3];

console.log("Array length: " + testArr.length);
let numAttempts = 10000;
let rndArray, getBin, binIsValid = false;

for (i=1; i<=numAttempts; i++) {

rndArray = shuffleArray(testArr);

getBin = binOutput(4.2, rndArray);
binIsValid = isBinValid(2.2, 4.2, getBin);

if (binIsValid === true) {
console.log("Completed in " + i + " attempts.");
break;
}

}

if (binIsValid === true) {
console.log(getBin);
} else {
console.log("No valid bin produced in " + numAttempts + " attempts.");
}

function binOutput(upperRange, rndVals) {
let newGroup = [], groupTotal = 0;

return rndVals.reduce((acc, val, i) => {
groupTotal = groupTotal + val;
if (groupTotal < upperRange) {
newGroup.push(val);
if (i === (rndVals.length-1)) {
acc.push(newGroup);
}
} else {
acc.push(newGroup);
newGroup = [];
newGroup.push(val);
groupTotal = val;
if (i === (rndVals.length-1)) {
acc.push(newGroup);
}
}
return acc;
}, []);
}

function isBinValid(lRange, uRange, bin) {
let binValid = true, groupTotal = 0;
bin.forEach(group => {
groupTotal = getGroupTotal(group);
if (groupTotal <= lRange || groupTotal >= uRange) binValid = false;
});
return binValid;
}

function getGroupTotal(groupArr) {
return groupArr.reduce((a, b) => a + b, 0);
}

function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
let temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}``````

CLICK HERE to find out more related problems solutions.

Scroll to Top