在这个问题中,我们正在尝试最小化所消耗的面积(例如:积分),其中包括垂直面积。
![enter image description here](https://istack.dev59.com/XqA0t.webp)
我使用 processing.js 和 HTML5 画布在 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
这是公共资源库,所以请随意创建分支并添加其他算法。由于它是一个有趣的问题,我将来可能会添加更多算法。
首先我想要简化问题,为此:
[a,b]
上的二次函数,其中a=0
,对于这个例子,b = 3
假设你有给定b
(区间的第二部分)和w
(段的宽度),那么你可以通过n=Floor[b/w]
找到总段数。在这种情况下,存在一种平凡的情况来最大化Riemann和和函数以获取第i个段的高度:f(b-(b*i)/(n+1))
。实际上这是一个假设,我不确定百分之百。
在闭区间[0, 3]
上的函数Sqrt[x]
的17段高度的最大化示例:
在这种情况下,段的高度函数是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}
你已经达到的是一个装箱问题,部分填充的箱子。
如果b
未知或我们的任务是找出使所有棍子形成初始束时最小可能的b
。那么我们至少可以将b
值限制为:
找到b
最简单的方法之一是在(上限-下限)/2
处取一个中心点,查看是否存在解。然后它成为新的更高或更低的限制,并且您重复该过程,直到达到所需的精度。
当您寻找b
时,您不需要确切的结果,而是次优的结果。如果您使用有效的算法找到相对接近实际b
的中心点,速度会更快。
例如:
这相当于有多个背包(假设这些块的“高度”相同,这意味着每条“线”都有一个背包),因此是装箱问题的一种实例。
我非常确定这等同于装箱问题:
非正式的降低难度方法:
假设x是最宽行的宽度,将箱子变成2x大,并为每一行创建一个占位元素,其大小为2x-rowWidth。因此,两个占位符元素无法放入一个箱子中。
要在抛物线背包上减少装箱问题,只需为所有大于所需箱子尺寸的行创建占位符元素,其大小为width-binsize。此外,为所有小于binsize的行添加填满整行的占位符。
这显然意味着你的问题是NP难问题。
其他想法可以在这里查看:http://en.wikipedia.org/wiki/Cutting_stock_problem
很可能这是01背包问题或装箱问题。这是一个NP难题,我很可能不理解这个问题,也无法向您解释,但您可以使用贪心算法进行优化。这里有一篇有用的文章http://www.developerfusion.com/article/5540/bin-packing,我用它来制作我的php类bin-packing在phpclasses.org上。