装箱问题 - 确定给定范围内一组值的最佳分组

Question

我的问题与我尝试根据组合大小（媒体文件）分组和合并的文件有关。一般来说，我有一个程序可以将多个文件组合成合并文件组。

用户可以select程序合并任意数量的文件。

程序会合并文件，并输出合并后的文件。

合并后的文件必须在一定的大小范围内。就我而言，2.2gb 到 4.2gb。

假设用户 select 有 10 个文件。我需要程序以尽可能最佳的方式组合文件。如果最后一个文件是 800mb，无法与前三个文件合并，但文件数组可以重组以合并 800mb 文件，我需要程序这样做。

这里有一个抽象程序来说明：

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

非常感谢任何帮助。

Answer 1

如果我理解得很好，我想你可以这样做：我希望这就是您要找的，编码真的很有趣 :)

您可以运行代码片段来查看结果

// ========== 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);

Answer 2

我不是数学高手，我知道这些装箱问题的解决方案可能会变得非常复杂。但是，在这种情况下，随机化输入非常有效。

因此，将初始数组随机化，然后根据下限和上限对数组进行线性分组，然后检查 bin 是否有效。

在这里，我有一个包含 50 个初始值的数组。我允许它最多尝试 10000 次，但它通常会在给定约束条件下（最小值：2.2，最大值：4.2）在前 500 次尝试中找到有效的 bin。很多时候要快得多。

经过多次测试，我没有一个负面结果：

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

装箱问题 - 确定给定范围内一组值的最佳分组

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

javascript

algorithm

grouping