algorithm - 抛物线背包

Question

假设我有一条抛物线。现在我还有一堆宽度相同的木棍(是的，我的绘画技巧太棒了!)。我如何将这些木棍堆叠在抛物线内，以便尽可能减少它使用的空间？我相信这属于 Knapsack problems 的类别，但是这个维基百科页面似乎并没有让我更接近真实世界的解决方案。这是一个 NP-Hard 问题吗？

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

Answer 1

我使用 JavaScript 编写了一个解决方案 processing.js和 HTML5 Canvas 。

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

根据输入的类型，排序算法可以在 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

这是一个公共(public)存储库，因此您可以随意分支并添加其他算法。我可能会在未来添加更多内容，因为这是一个有趣的问题。