将数字分组到大小为 X 的最少数量的存储桶中

Group numbers into least number of buckets of size X

本文关键字：存储数字小为更新时间：2023-09-26

查找有关如何将数字集合分组到大小为 X 的最少数量的存储桶中的示例。

例如，如果我有这个数字数组：

var myCompartments = { 4, 6, 2, 8, 6, 3, 1, 1, 4, 2, 7, 2, 8, 3, 9 };

我想使用以下存储桶大小将它们分组到存储桶中：

var bucketSize = 12;

我正在寻找的是一个函数或算法，它将这些分组到与 bucketSize 匹配的最少数量的存储桶中，然后将剩余的数字(不适合(放在自己的列表中。

我希望看到的示例结果：

var buckets = [ 
    { 4, 6, 2 },
    { 8, 3, 1 },
    { 6, 4, 2 },
    { 9, 3 }
];
var leftovers = {1, 7, 2, 8 };

如果它可以输出类似于示例结果，那就太好了。"剩余"列表中的项目数量越少越好。

到目前为止，我所拥有的只是循环浏览集合并在有空间的情况下添加到存储桶中，如果没有空间，则创建一个新存储桶。这是低效的，最终会得到很多部分已满的存储桶。我使用的是angularJS，所以这里使用了一些快捷方法：

var bucketSize = 12;
var buckets = [
    { remainingCapacity: bucketSize, items: [] }
];
var myCompartments = [
    { isAssigned: false, size: 4 },   
    { isAssigned: false, size: 6 },   
    { isAssigned: false, size: 2 },   
    { isAssigned: false, size: 8 },   
    { isAssigned: false, size: 6 },   
    { isAssigned: false, size: 3 },   
    { isAssigned: false, size: 1 },   
    { isAssigned: false, size: 1 },   
    { isAssigned: false, size: 4 },   
    { isAssigned: false, size: 2 },   
    { isAssigned: false, size: 7 },   
    { isAssigned: false, size: 2 },   
    { isAssigned: false, size: 8 },
    { isAssigned: false, size: 3 },
    { isAssigned: false, size: 9 }
];
myCompartments.forEach(function(compartment) {
    buckets.forEach(function(bucket) {
        if (bucket.remainingCapacity >= compartment.size && !compartment.isAssigned) {
            bucket.remainingCapacity -= compartment.size;
            compartment.isAssigned = true;
            bucket.items.push(compartment);
        }
    });
    // if compartment still not assigned, add to a new bucket
    if (!compartment.isAssigned && bucketSize >= compartment.size) {
        compartment.isAssigned = true;
        var remainingCapacity = bucketSize - compartment.size;
        var newBucket = { remainingCapacity: remainingCapacity, items: [] };
        newBucket.items.push(compartment);
        buckets.push(newBucket);
    }
});

编辑 - 我创建了一个 plunker，用于输出创建的存储桶进行调试

这并不漂亮，但它有效。

它多次遍历数据，每次都对数组值进行随机排序，以尝试找到将项目分组到特定大小的存储桶中的更好顺序。

普伦克

$(function() {
  var bucketSize = 12;  
  var buckets = [{
    remainingCapacity: bucketSize,
    pieces: []
  }];
  var pieces = [
      { isAssigned: false, size: 4 },     
      { isAssigned: false, size: 6 },   
      { isAssigned: false, size: 2 },   
      { isAssigned: false, size: 8 },   
      { isAssigned: false, size: 6 },   
      { isAssigned: false, size: 3 },   
      { isAssigned: false, size: 1 },   
      { isAssigned: false, size: 1 },   
      { isAssigned: false, size: 4 },   
      { isAssigned: false, size: 2 },   
      { isAssigned: false, size: 7 },   
      { isAssigned: false, size: 2 },   
      { isAssigned: false, size: 8 },
      { isAssigned: false, size: 3 },
      { isAssigned: false, size: 9 }
  ];
  var unassignedCount = pieces.length;
  var count = 1000;
  while (count--) {
    shuffle(pieces);  
    var p = pieces.length;
    var b = 0;
    while (p--) {
      var piece = pieces[p];
      b = buckets.length;
      while (b--) {
        var bucket = buckets[b];
        // add to bucket if there is room and piece is not assigned
        if (bucket.remainingCapacity >= piece.size && !piece.isAssigned) {
          bucket.remainingCapacity -= piece.size;
          piece.isAssigned = true;
          bucket.pieces.push(piece);
        }
      }
      // if not assigned and not bigger than bucketSize, add to new bucket
      if (!piece.isAssigned && piece.size <= bucketSize) {
        var remainingCapacity = bucketSize - piece.size;
        var newBucket = {
          remainingCapacity: remainingCapacity,
          pieces: []
        };
        newBucket.pieces.push(piece);
        buckets.push(newBucket);
      }
      pieces.splice(p, 1);
    }
    b = buckets.length;
    while (b--) {
      var bucket = buckets[b];
      if (bucket.remainingCapacity > 0) {
        p = bucket.pieces.length;
        while (p--) {
          var piece = bucket.pieces[p];
          piece.isAssigned = false;
          pieces.push(piece);
          bucket.pieces.splice(p, 1);
        }
        buckets.splice(b, 1);
      }
    }  
    unassignedCount = pieces.length;
  }

  function shuffle(array) {
    var currentIndex = array.length,
      temporaryValue, randomIndex;
    // While there remain elements to shuffle...
    while (0 !== currentIndex) {
      // Pick a remaining element...
      randomIndex = Math.floor(Math.random() * currentIndex);
      currentIndex -= 1;
      // And swap it with the current element.
      temporaryValue = array[currentIndex];
      array[currentIndex] = array[randomIndex];
      array[randomIndex] = temporaryValue;
    }
    return array;
  }
  document.write('number of buckets: ' + buckets.length + '<br><br>');
  document.write('number of remaining pieces: ' + unassignedCount + '<br>    <br>');
  buckets.forEach(function(bucket) {
    document.write('bucket:<br>');
    document.write('remaining capacity: ' + bucket.remainingCapacity + '<br>');
    document.write('items:<br>');
    bucket.pieces.forEach(function(piece) {
      document.write('size: ' + piece.size + '<br>');
    });
    document.write('<br>');
  });
  document.write('<br>leftovers: ');
  pieces.forEach(function(piece) {
    if (!piece.isAssigned) {
      document.write(piece.size + ', ');
    }
  });
});

如果其他人有更优雅的解决方案，我会很想看看你想出了什么！谢谢。