在固定空间内分配盒子的算法

Question

我有许多任意宽度的盒子。每个盒子的宽度可能受限于下限和上限。现在我想用这些规则堆叠这些盒子以适合固定数量的空间：

1. 可以不留空的空间。
2. 每个盒子的宽度可以在其范围内改变。
3. 所有盒子的宽度应尽可能均匀。

作为一个先决条件，假设并非所有的盒子都被限制排除解决方案。

例如，假设我有460个单位的可用空间和五盒的。一个方框具有下界200，和一个盒具有两个下限和上限的20的可用空间内分发这些框后，结果如下所示：

的黑色数字在这个例子中给出，蓝色数字是预期的结果。我正在寻找一种产生这个结果的算法。有人能指出我解决这个问题的正确方向吗？

Answer 1

• 在0和w之间的二进制搜索（在您的示例中= 460）。我们称之为target-w。
  • 对于每个框，如果target-w瀑布内部[w_min, w_max]，使用target-w作为框选择的宽度。否则，根据情况选择w_min或w_max。
  • 总结所有框的选定宽度。
  • 如果总和大于w大，我们需要一个更小的target-w。否则，我们需要更小的target-w。
  • （继续与二进制搜索。）