对加权元素进行分区，限制总分区权重

Question

给定一个较大的正整数“权重”数组（例如[ 2145, 8371, 125, 10565, ... ]）和一个正整数“权重限制”例如15000，我要使用以下条件将权重划分为一个或多个较小的数组：

1. 我想最小化分区数。
2. 没有一个分区的总和不能超过重量限制。（请注意，单个重量不会超过此限制。）

我怀疑这个问题的复杂程度很高。作为答案，我感兴趣：

1. 最佳解决方案
2. 并非最佳选择，但运行速度很快（近似）的解决方案

当前的非最佳方法：（基本贪婪算法； JavaScript）

function minimizePartitions(weights, weightLimit) {
  let currentPartition = [];
  let currentSum = 0;
  let partitions = [ currentPartition ];
  
  for (let weight of weights) {
    if (currentSum + weight > weightLimit) {
      currentPartition = [];
      currentSum = 0;
      partitions.push(currentPartition);
    }
    
    currentPartition.push(weight);
    currentSum += weight;
  }
  
  return partitions;
}

let weights = [3242, 987, 1222, 7299, 400, 10542, 10678, 513, 3977];
console.log(minimizePartitions(weights, 15000));

Answer 1

这是一个装箱问题，已知是NP难的。

为了快速近似，我建议从最大到最小进行排序，然后将每个元素放入适合的bin中，最接近满的元素。