抛物线背包

Question

让我们说我有抛物线.现在我也有一堆宽度相同的棒(是的,我的绘画技巧太棒了!).如何在抛物线内堆叠这些木棍,以便尽可能减少其使用的空间？我认为这属于背包问题类别,但这个维基百科页面似乎并没有让我更接近现实世界的解决方案.这是NP-Hard问题吗？

在这个问题中,我们试图最小化消耗的区域量(例如:积分),其中包括垂直区域.

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], where a = 0,对于这个例子b = 3

假设你给出了b(间隔的第二部分)和w(段的宽度),那么你可以找到段的总数n=Floor[b/w].在这种情况下,存在一个微不足道的情况,以最大化黎曼和和函数以得到第i个段高度:f(b-(b*i)/(n+1))).实际上这是一个假设,我不是百分百肯定.

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

在这种情况下,段高度函数是Re[Sqrt[3-3*Range[1,17]/18]],并且值是:

• 确切形式:

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

• 近似形式:

{1.6832508230603465,1.632993161855452,1.5811388300841898,1.5275252316519468,1.4719601443879744,1.4142135623730951,1.35400640077266,1.2909944487358056,1.224744871391589,1.1547005383792517,1.0801234497346435,1,0.9128709291752769,0.816496580927726,0.7071067811865475,0.5773502691896258,0.4082482904638631}

您存档的是Bin-Packing问题,部分填充箱.

寻找b

如果b未知或我们的任务是找到最小可能的b所有棒形成初始束适合.然后我们可以将至少b值限制为:

1. 下限:如果段高的总和=杆高的总和
2. 上限:段数=棒数 最长棒<最长段高度

如果解决方案存在,最简单的方法之一就是找到b一个支点(higher limit-lower limit)/2.然后它变为新的上限或下限,并重复该过程,直到满足所需的精度.

当你在寻找b你时,你不需要精确的结果,但是不是最理想的,如果你使用有效的算法来找到相对接近的实际枢轴点,它会快得多b.

例如:

• 按长度排序:最大到最小
• 开始'把最大的物品'放入你的第一个装箱中

Answer 3

这相当于有多个背包(假设这些块是相同的'高度',这意味着每个'线'有一个背包),因此是垃圾箱包装问题的一个实例.

见http://en.wikipedia.org/wiki/Bin_packing