抛物线背包

Question

假设我有一条抛物线。现在我也有了一堆宽度相同的棍子(是的，我的绘画技巧非常棒！)。我如何在抛物线中堆叠这些棒，以便尽可能地最小化它所使用的空间？我相信这属于Knapsack problems的范畴，但这个维基百科页面似乎并没有让我更接近现实世界的解决方案。这是NP难问题吗？

在这个问题中，我们试图最小化消耗的面积(例如:积分)，其中包括垂直面积。

​

​

Answer 1

我使用processing.js和HTML5 canvas在JavaScript中设计了一个解决方案。

如果你想创建自己的解决方案，这个项目应该是一个很好的起点。我添加了两个算法。一个是从最大到最小对输入块进行排序，另一个是随机排列列表。然后，尝试从底部(最小的桶)开始将每个项目放入桶中，并向上移动，直到有足够的空间容纳为止。

根据输入类型的不同，排序算法可以在O(n^2)内获得较好的结果。下面是一个排序输出的示例。

​

​

这是按顺序插入的算法。

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

github上的项目- https://github.com/gradbot/Parabolic-Knapsack

这是一个公共代码库，所以可以随意分支并添加其他算法。我可能会在将来添加更多，因为这是一个有趣的问题。

Answer 2

这相当于有多个背包(假设这些块的“高度”相同，这意味着每条“线”都有一个背包)，因此是装箱问题的一个实例。

请参阅http://en.wikipedia.org/wiki/Bin_packing

Answer 3

我如何在抛物线中堆叠这些棒，以便尽可能地最小化(垂直)空间？

只需像处理任何其他装箱问题一样处理它。我会使用元启发式算法(如禁忌搜索、模拟退火等)因为这些算法不是特定于问题的。

例如，如果我在Drools Planner中从我的Cloud Balance problem (=一种装箱形式)开始。如果所有的棍子都有相同的高度，并且两根棍子之间没有垂直间距，那么我就不需要做太多的改变：

• 将Computer重命名为ParabolicRow。删除它的属性(cpu、内存、带宽)。给它一个唯一的level (其中0是最低的一行)。Create a ParabolicRows.
• Rename ParabolicRows.

to StickAssignment

• Rewrite ProcessAssignement to Stick

• Rename Process to ParabolicRows.

• RenameParabolicRows.

检查是否有足够的空间容纳分配给软约束的所有Process的总和，以最小化所有ProcessAssignement中最高的Sticks