用于填充插槽的算法

Question

我正在寻找一种算法来填充多个插槽，这些插槽已经被部分填充。

• 已知当前的填充水平和可用数量
• 结果水平应尽可能相等，但现有的水平不能降低
• 插槽从左到右填充，因此如果无法实现相等水平，则左侧插槽会获得更高的水平

上图展示了六个例子，每列代表一个插槽。灰色区域已经填满，蓝色区域是新元素的期望位置。

示例 http://img695.imageshack.us/img695/6529/fill.png

---

我可以遍历我的插槽，并将最低的插槽数量增加1，直到可用数量被消耗，但是我想知道如何实际计算新的填充水平。

我将使用SQL/PLSQL来实现这个功能，其他代码也同样适用 :)

- Peter Lang

---

尝试理解图像/问题：蓝色鼻子是可用插槽还是已经被占用的插槽？此外，每个条形图都代表一个插槽吗？“新填充水平”是什么意思？ - vad

@Anon：灰色区域已经被占据，蓝色区域是新元素的预期位置。所谓“新填充水平”是指插槽（即垂直线）的新高度。希望这可以帮到你！ - Peter Lang

那么，每一列都是一个插槽吗？您的图像在列之间有间距，这似乎表明列的组是插槽。 - vad

@Anon：是的，每一列都是一个插槽。我添加了图像的描述，希望现在更清晰了。 - Peter Lang

首先，“尽可能相等”应该被正式定义。有几种可行的定义，例如：最小化插槽之间的最大差异；最小化已更改的插槽之间的最大差异；最小化平均差异等。 - Marco

Answer 1

这很简单。

你可以将它想象成倒水并让它填满，除了某些情况 *。

1. 排序。您还可以使用优先队列。
2. 跟踪当前最小列的数量。
3. 获取第二个最小列的最小列。
4. 用可用项目的数量或最多到第二个最小列来填充最小列。
5. 增加当前最小列的计数。
6. 重复步骤4直到所有列都处于相同的水平，除了使用可用项目的数量或delta（第二个最小值-第一个最小值）乘以当前最小列的数量。如果可用项目的数量不足，只需进行简单的数学运算（除法和余数）来填充列，并使用余数从左侧填充。
7. 当所有列处于相同的水平时，请使用步骤6中描述的简单数学部分。

你应该没问题了。

此算法的运行时间为O(n log n)。

*某些情况下这没有意义，但您仍然希望这样做：

 #
 #
##
###
###

在这种情况下，您需要填写第三列，然后是第一列，接着是第二列，但当然这并不是像灌水一样简单。

- Larry

Answer 2

也许一个带有随机化的贪心算法来打破平局就足够了。

假设你需要填充的插槽数量为n。

步骤1：循环遍历列，找出已填充插槽最少的列。跳过已经填满的列。

步骤2：如果在步骤1中找到的列数大于1，则随机选择其中一列。

步骤3：设置n = n-1。

重复步骤1、2和3，直到n = 0或没有空列为止。

- vad

Answer 3

1. 将列按照起始水平从低到高排序。
2. 计算（排序后的）列的累积起始使用量。
3. 为每一列计算通过填充到该列高度将使用多少新填充物。使用量将是该列高度乘以列索引，减去其前面所有列的累积起始使用量。
4. 选择索引为i的列，它将使用最多的新填充物而不超过限制。将所有列填满到第i列的高度（这将使用步骤＃3中计算出的列i的填充量），然后剩余的填充物均匀地分配在前i列上，每列加上一个额外的填充物，直到填满所有剩余的填充物。
5. 撤销列的排序以获得结果。

这应该需要与列数成线性时间（与填充物的数量无关）。

- Keith Randall

Answer 4

听起来像是经典的背包问题 有许多不同的语言解决方案，使用不同的算法在罗塞塔代码尽管我不确定是否有PL/SQL相关内容

- Mark Baker

---

我看不出与背包问题的联系。我没有任何重量/价值可供选择，我需要找出有多少个物品放在哪个位置。 - Peter Lang

你的所有物品都具有相同的重量和价值：查看背包问题的特定子集/变体，例如装箱问题（多个背包）和分区问题... 这些都在维基百科页面上提到。 - Mark Baker