假设你有k种石头和m种石头
你有第一种类型的f1石头，第二种类型的f2石头等等。
（即总和（f_i）=k）。
另外，我们得到了一个正整数r。
所需的最小桶数是多少，这样我们就可以将石头类型分配到每个桶大小不超过r的桶中？
（我们也知道，对于每个i，f_i这个问题实际上是某种装箱，所以我不确定它有一个确切的答案，但我们能给它一个上限吗？
一个简单上界的例子是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类型和一个bucket中的一个z类型放在一起{我们有z个这样的bucket}。
把剩下的Y型一个装在桶里。
从y>z开始，我们一直使用x+y桶，从3x+2y+z=k=>x+y如果（z>=y）{第二种情况}：
很容易看出，我们可以把所有的石头放在K/3桶里（每个桶可以装满，正好包含3块石头）。
另外，对于r=3，这个限制是紧的（如果x=z=0和y=k/2，那么我们正好需要k/2桶）。
现在的问题是：k/2 bucket bound是否适用于所有r值？
我可以证明2K/（R+1）桶的下限（即一个紧实例），但它离K/2很远。有人能勒紧绳子吗？
最佳答案
您可以使用first-fit algorithm解决装箱问题，几乎不需要进行任何修改：
生成一个包含整数的列表，每个整数代表每种类型的结石数量。
按降序排列列表。
创建新bucket
从头到尾运行L，如果向bucket添加m的当前元素不超过L，则添加到bucket并将其从L中移除。
如果r为空，则返回桶数否则返回步骤3。
该算法近似于L，这是相当不错的，在大多数情况下给出了很好的结果。
该算法的运行类型为L如果未给出11/9*OPT + 6/9，则要创建列表，需要计算每种类型的结石数量，这需要O(m log m)时间，整个过程将需要m时间。