Question

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;
}

Leave a Comment Cancel Reply