假设您有k种石头和m种石头类型你有第一种类型的f1石头，第二种类型的f2石头，依此类推
(即sum(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块石头的类型的数量。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桶是否适用于所有r值？
我可以展示2k/(r+1)桶的下界(即紧实例)，但它离k/2很远。有人能拉紧绳子吗？
您可以使用第一次拟合算法来解决装箱问题，几乎不需要任何修改：
- 生成一个包含
m整数的列表L，每个整数表示每种类型的石头数量 - 按降序对列表进行排序
- 创建新存储桶
- 从开始到结束运行
L，如果将L的当前元素添加到bucket中没有超过r，则添加到bucket中并将其从L中移除 - 如果
L为空，则返回bucket的个数。否则返回步骤3
该算法是11/9*OPT + 6/9的近似值，它相当不错，并且在大多数情况下给出了非常好的结果。
该算法的运行类型为O(m log m)。如果没有给出m，则创建列表需要计算每种类型的石头数量，这需要O(L)时间，整个过程将需要O((m log m) + L)时间。