对加权元素进行分区，限制总分区权重 [英] Partitioning weighted elements with a restriction on total partition weight

问题描述

给出大量的正整数权重"，例如 [2145，8371，125，10565，...] ，以及一个正整数权重限制"，例如15000，我想使用以下条件将权重划分为一个或多个较小的数组:

Given a large array of positive integer "weights", e.g. [ 2145, 8371, 125, 10565, ... ], and a positive integer "weight limit", e.g. 15000, I want to partition the weights into one or more smaller arrays, with the following criteria:

1. 我要尽量减少分区数.
2. 没有一个分区的总和不能超过重量限制.(请注意，单个重量不会超过此限制.)

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

I suspect this problem has a high complexity class. As answers, I'm interested in:

1. 最佳解决方案
2. 不是最佳选择，但是运行速度很快(近似)的解决方案

当前非最佳方法:(基本贪婪算法； JavaScript)

Current non-optimal approach: (Basic greedy algorithm; 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));

推荐答案

这是一个 bin-packing问题，并且已知是NP-hard.

This is a bin-packing problem and is known to be NP-hard.

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

For a quick approximation I would suggest sorting from largest to smallest, and then putting each element in the bin that it fits in which is closest to full.

这篇关于对加权元素进行分区，限制总分区权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！