javascript - 对总分区权重有限制的分区加权元素

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

这是一个 bin-packing problem并且已知是 NP 难的。

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