抛物面背包

可以说我有一个抛物线。 现在我也有一堆棍子都是一样的宽度（是的，我的绘画技能是惊人的！）。 我怎样才能把这些棍子放在抛物线内，这样我就尽可能地减less了它所用的空间？ 我相信这属于背包问题 ，但这个维基百科页面似乎并没有让我更接近现实世界的解决scheme。 这是一个NP难题？

在这个问题中，我们试图尽量减less消耗的面积（例如：积分），其中包括垂直面积。

Answer 1

我使用processing.js和HTML5canvas在JavaScript中制作了一个解决scheme。

如果你想创build自己的解决scheme，这个项目应该是一个很好的起点。 我添加了两个algorithm。 一个将input块从最大到最小的sorting，另一个随机地对列表进行sorting。 然后试图将每个物品从底部（最小的桶）开始放入桶中并向上移动，直到其具有足够的空间以适应。

根据input的types，sortingalgorithm可以在O（n ^ 2）中给出好的结果。 这是一个sorting输出的例子。

这里是顺序插入algorithm。

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

这是一个公共回购，所以随意分支和添加其他algorithm。 我将来可能会增加更多，因为这是一个有趣的问题。

Answer 2

简化

首先，我想简化问题，做到这一点：

• 我切换轴并将它们添加到对方，这导致了x2的增长
• 我假设它是一个闭区间[a, b], where a = 0抛物线[a, b], where a = 0 ，对于这个例子b = 3

假设你给出了b （区间的第二部分）和w （区段的宽度），那么你可以通过n=Floor[b/w]find区段总数。 在这种情况下，存在一个微不足道的情况来最大化黎曼和和函数来得到第i个段的高度为： f(b-(b*i)/(n+1))) 。 其实这是一个假设，我不是100％肯定的。

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

在这种情况下的段高度函数是Re[Sqrt[3-3*Range[1,17]/18]] ，值为：

• 确切forms：

Sqrt [17/6]，2 Sqrt [2/3]，Sqrt [5/2]，Sqrt [7/3]，Sqrt [13/6]，Sqrt [2]，Sqrt [11/6]，Sqrt 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]}

• 近似forms：

{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的问题 ，部分填满的bin。

寻找b

如果b是未知的或者我们的任务是在所有棒形成初始束合适的情况下find尽可能小的b 。 那么我们可以将b值限制为：

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

findb的最简单的方法之一是在(higher limit-lower limit)/2find一个关键点，找出是否存在解。 然后它变成新的更高或更低的限制，重复这个过程直到满足所需的精度。

---

当你正在寻找b你不需要精确的结果，但是不是最理想的，如果你使用高效的algorithm来find相对靠近实际b枢轴点，速度会更快。

例如：

• 按长度sorting：从最大到最小
• 开始“把最大的物品”放在你的身体上

Answer 3

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

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

Answer 4

我怎样才能把这些棍子放在抛物线内，这样我就尽可能地减less了它所使用的（垂直）空间？

只要处理它像任何其他斌包装问题。 我会抛出元启发式 （如禁忌search ， 模拟退火 ，…），因为这些algorithm不是问题特定的。

例如，如果我从Drools Planner的 云平衡问题 （=一种Bin包装forms）开始。 如果所有的棍棒都有相同的高度，两根棍子之间没有垂直空间，那么我就不需要改变了：

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

Answer 5

我很确定它相当于装箱：

非正式的减less

为最宽行的宽度，使箱子2x大并为每一行创build一个2x-行宽大的占位符元素。 所以两个占位符元素不能打包成一个bin。

为了减less抛物面背包的装箱，你只需要为大于宽度为binsize大小的所有行创build占位符元素。 此外，为小于binsize的所有行添加占位符，填充整行。

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

对于其他想法也许看： http : //en.wikipedia.org/wiki/Cutting_stock_problem

Answer 6

这很可能是1-0背包或垃圾箱问题。 这是一个NP难题，很可能这个问题我不明白，我不能向你解释，但你可以用贪婪的algorithm进行优化。 这里是一个关于它的有用的文章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单位）

你当然可以扩大“多仓包装”的方法，并testing任意小增量。 （例如：运行多个binpacking方法，水平从0.0,0.1,0.2，… 0.9开始），然后select最好的结果，但似乎你会卡住无限的时间，除非你有一些方法（或者更准确地说，你所有的'行'都是正确的，它们所包含的内容是正确的，在这一点上，你可以把它们移到下一个边界，直到它们到达抛物线的边缘）

另外，OP没有规定棍子必须水平放置 – 尽pipeOP可能暗示着那些甜美的图画。

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

我说只是把它们扔在那里，摇动它们;）