Bin packing problem - Determine optimal grouping of set of values for a given range

user_14003904 0
Viewed 100

My problem relates to files I’m trying to group and merge based on combined size (media files). In general, I have a program that will combine multiple files into groups of merged files.

The user may select any amount of files for the program to combine.

The program will combine the files, and output the merged files.

The merged files must be within a certain size range. In my case, 2.2gb to 4.2gb.

So let’s say the user selects 10 files. I need the program to then combine the files in the most optimal way possible. If the last file is 800mb, and won’t fit in the merge with the previous three, but the array of files COULD have been reorganized to incorporate the 800mb file, I need the program to do so.

Here’s an abstract program that illustrates:

console.log(output(2.2, 4.2, [1, .5, .4, 1.2, 2.2, 1.1, 1.7, 1.8, .2, .8]));

function output(lowerRange, upperRange, values) {

    let groups = [];
    
    
    // This works, but would output with a hanging .8 at the end. 
    groups = [ [1, .5, .4, 1.2], [2.2, 1.1], [1.7, 1.8, .2], [.8] ];

    // This reorganizes to incorporate .8 in a more optimal way by shifting things around.
    groups = [ [1, .5, .4, 1.2], [2.2, 1.1, .8], [1.7, 1.8, .2] ];

    return groups;
}

Any help much appreciated.

grouping algorithm javascript
2 Answers

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

user_90408660

If i understand well, i guess you can do something like this : I hope this is what you were looking for, it was really fun to code :)

You can run the code snippet to see result

// ========== Function definition ==========
function output(storage, filesToStore, min, max) {

    for (file of filesToStore) {
      
      if (storage.length == 0) {
        let chunk = []
        storage.push(chunk)
      }
      
      let fileIsStored = false
      for (chunk of storage) {
        if (hasChunkEnoughAvailableSpace(chunk, file, min, max)) {
          chunk.push(file)
          fileIsStored = true
        }
      }
      
      if (!fileIsStored) {
        storage.push([file])
      }
    }
}

function hasChunkEnoughAvailableSpace(chunk, fileSize, min, max) {
  let totalSize = chunk.reduce((a,b)=>a+b, 0) // This is just a "sum"
  
  return fileSize < max - totalSize; // Is file size less than remaining space
}


// ========== Core ==========

let storage = [];

// I juste generate random numbers, but that is the same thing as file sizes
let filesToStore = Array.from({length: 40}, () => Math.floor(Math.random() * 60));

// For my needs, just adapte it at yours
let min = 20
let max = 35


output(storage, filesToStore, min, max)
console.log(storage);

user_145553320
Related