algorithm - 将石头分配到桶中(不重要)/Integer Bin Packing Upper bound

Question

假设你有 k 种石头和 m 种石头您有第一种类型的 f1 石头，第二种类型的 f2 石头，依此类推。

(即总和(f_i)= k)。

另外，给定一个正整数r。

最少需要多少个桶，这样我们才能将石头类型分配到每个桶的大小不超过 r 的桶中？(我们也知道对于每个 i，f_i <= r)。

这个问题实际上是某种装箱问题，所以我不确定它是否有确切的答案，但我们可以给它一个上限吗？

一个简单上限的例子是 m，因为这将允许我们将每种石头类型打包成他自己的桶。

一个无效边界的例子是 k/r。原因是如果k=9，r=3，我们有5种石头，f1=2，f2=2，f3=2，f4=2，f5=1，

那么无论我们如何划分石头类型，都必须有一个大小 >= 4 的桶。

所有同类型的石头都必须放到同一个桶中。

有什么建议:)？

编辑:m 和 f_i 是未知的，我正在寻找一个边界，它使我能够为所有 (m,f_i) 组合分配石头。

另一个例子:假设 r = 3。我将证明 k/2 个桶就足够了:

让我们用 x 表示有 3 个 gem 的类型数。y 表示恰好有 2 个石子的类型数，z 表示单石子类型的数量。

根据定义:3x + 2y + z = k。我们可以为 3 石类型分配 x 个桶。

如果 (y > z) {第一种情况}:将其中一种 y 类型与其中一种 z 类型一起放入桶中{我们有 z 个这样的桶}。

将其余的 y 类型放入一个桶中。

因为 y > z 我们正好使用了 x+y 个桶，并且因为 3x + 2y + z = k => x+y <= k/2。

如果 (z >= y) {第二种情况}:很容易看出，我们可以将所有石子装在 k/3 个桶中(每个桶都可以装满，正好包含 3 个石子)。

此外，对于 r=3，这将它限制得很紧(如果 x=z=0 和 y=k/2，那么我们正好需要 k/2 个桶)。

现在的问题是:k/2 个桶绑定(bind)是否适用于所有 r 个值？

我可以证明 2k/(r+1) 个桶的下限(即紧实例)，但它与 k/2 相去甚远。任何人都可以收紧界限吗？

Answer 1

您可以使用 first-fit algorithm对于几乎不需要修改的装箱问题:

1. 生成一个包含 m 个整数的列表 L，每个整数代表每种类型的石头的数量。
2. 按降序排列列表。
3. 创建一个新的桶
4. 从头到尾遍历L，如果将L的当前元素加入桶中，不超过r，则添加到桶中并将其从 L 中删除。
5. 如果 L 为空，则返回桶数。否则返回第 3 步。

这个算法是 11/9*OPT + 6/9 的近似值，这是相当不错的，在大多数情况下给出了很好的结果。

该算法的运行类型为O(m log m)。如果未给出 m，要创建列表，您需要计算每种类型的石头数量，这需要 O(L) 时间，整个过程将花费 O((m log m) + L) 时间。