抛物线背包

Question

假设我有一条抛物线。现在我还有一堆宽度相同的棍子（是的，我的绘画技巧太棒了！）。如何将这些木棍堆叠在抛物线内，以便尽可能减少其使用的空间？我相信这属于背包问题的类别，但这个维基百科页面似乎没有让我更接近现实世界的解决方案。这是一个 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

简化

首先我想简化问题，为此：

• 我切换轴并将它们彼此相加，这会导致 x2 增长
• 我假设它是闭区间上的抛物线[a, b]，其中 a = 0 ，对于本例 b = 3

假设您给出了 b （间隔的第二部分）和 w （间隔的宽度）一个段），那么您可以通过n=Floor[b/w]找到段的总数。在这种情况下，存在一个最大化黎曼和的简单情况，并且获得第 i 段高度的函数是：f(b-(b*i)/(n+1)))。实际上这是一个假设，我并不能100%确定。

函数 Sqrt[x] 实值的闭区间 [0, 3] 上 17 段的最大示例：

本例中的段 heights 函数为 Re[Sqrt[3-3*范围[1,17]/18]]，值为：

• 精确形式：

{Sqrt[17/6], 2 Sqrt[2/3], Sqrt[5/2],
平方[7/3]、平方[13/6]、平方[2]、
平方[11/6]、平方[5/3]、平方[3/2]、
2/平方[3]、平方[7/6]、1、平方[5/6]、
平方[2/3]、1/平方[2]、1/平方[3]、
1/平方[6]}

• 近似形式：

{1.6832508230603465，
1.632993161855452、1.5811388300841898、1.5275252316519468、1.4719601443879744、1.4142135623730951、1.35400640077266、1.290 9944487358056、1.224744871391589、1.1547005383792517、1.0801234497346435、1、0.9128709291752769、0.816496580927726、 7811865475, 0.5773502691896258, 0.4082482904638631}

What you have archived is a Bin-Packing problem,带有部分填充的垃圾箱。

查找 b

如果 b 未知，或者我们的任务是在所有木棍形成初始束拟合的情况下找到尽可能小的 b。然后我们可以将至少 b 值限制为：

1. 下限：如果段高度总和 = 棒高度总和
2. 上限：段数 = 棒数 最长棒 < ;最长线段高度

查找 b 的最简单方法之一是在 (上限-下限)/2 处进行枢轴查找是否存在解。然后它变成新的上限或下限，您重复该过程直到满足所需的精度。

---

当您寻找b时，您不需要精确的结果，但不是最优的，如果您使用有效的算法来找到与实际b相对接近的枢轴点，速度会快得多。

例如：

• 按长度对棍子进行排序：从最大到最小
• 开始“将最大的物品”放入适合您的第一个箱子中

Answer 3

这相当于有多个背包（假设这些块具有相同的“高度”，这意味着每“行”有一个背包），因此是装箱问题的一个实例。

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

Answer 4

如何将这些木棍堆叠在抛物线内，以便尽可能减少其使用的（垂直）空间？

就像处理任何其他装箱问题一样处理它。我会在其上添加元启发式算法（例如禁忌搜索、模拟退火……），因为这些算法不是问题具体的。

例如，如果我从我的云平衡问题（= Bin Packing 的一种形式）位于 Drools Planner 中。如果所有的棍子都具有相同的高度，并且彼此顶部的 2 根棍子之间没有垂直空间，则无需进行太多更改：

• 将 Computer 重命名为 ParabolicRow 。删除它的属性（CPU、内存、带宽）。给它一个唯一的级别（其中0是最低行）。创建多个 ParabolicRows。
• 将 Process 重命名为 Stick
• 将 ProcessAssignment 重命名为 StickAssignment
• 重写硬约束，以便检查是否有足够的空间容纳总和分配给 ParabolicRow 的所有 Sticks。
• 重写软约束以最小化所有ParabolicRows 的最高级别。

Answer 5

我非常确定它相当于装箱：

非正式减少

最宽行的宽度，使箱变大 2 倍，并为每一行创建一个占位符元素，其大小为 2 倍行宽度。因此两个占位符元素不能打包到一个 bin 中。

为了减少抛物线背包上的装箱，您只需为所有大于所需 binsize 且大小为 width-binsize 的行创建占位符元素。此外，为小于 binsize 的所有行添加占位符，以填充整行。

这显然意味着你的问题是 NP 难的。

对于其他想法，请查看这里：http://en.wikipedia.org/wiki/Cutting_stock_problem

Answer 6

这很可能是 1-0 背包问题或装箱问题。这是一个 NP 难题，很可能这个问题我不明白，我无法向你解释，但你可以用贪心算法进行优化。这是一篇关于它的有用文章 http://www.developerfusion.com/article/5540/ bin-packing，我用它来在 phpclasses.org 上对我的 php 类进行 bin-packing。

Answer 7

向那些提到水平可以处于不同高度这一事实的人提供支持（例如：假设棍子有 1 个“粗”，水平 1 从 0.1 单位变为 1.1 单位，或者可以从 0.2 单位变为 1.2 单位）

您可以课程扩展“多箱包装”方法并测试任意小的增量。 （例如：运行级别从 0.0、0.1、0.2、... 0.9 开始的多重装箱方法），然后选择最佳结果，但除非您有某种方法，否则您似乎会陷入无限长的计算中验证你是否得到了“正确”的结果（或者更准确地说，你的所有“行”所包含的内容都是正确的，此时你可以将它们向下移动，直到它们遇到抛物线的边缘）

此外， OP 没有明确指出木棍必须水平放置 - 尽管OP 可能用那些可爱的图画暗示了这一点。

我不知道如何最佳地解决这样的问题，但我敢打赌，在某些情况下，您可以随机放置木棍，然后测试它们是否在抛物线“内部”，并且它会击败任何仅依赖于水平的方法行。
（考虑一下我们试图用一根长棍子填充一条狭窄抛物线的情况。）

我说只需将它们全部扔在那里并摇动它们即可；）