javascript - 不同大小的块最好分配给固定大小的桶

Question

我有一个有趣的（或者可能是简单的）问题要解决。在桶之间分配不同大小的块（比如任何实数，如 0.5 或 50）。存储桶大小始终为 64。

要解决的问题是以这样一种方式分配块，即浪费桶中最少的空间。

寻求简单的解决方案，只需遍历桶并将第 n 个元素推入该块可以放入的第一个桶中。如果没有适合该元素的存储桶 - 将创建新存储桶。

有没有更好的方法来做到这一点，或者天真的解决方案也是最佳解决方案？

标签： javascriptalgorithm

Answer 1

这是一个数学上复杂的问题，称为装箱问题。

您可能找不到实现最佳解决方案的简单方法。 本页提到了一种解决方案，即始终将块放在可以容纳它的最满的桶中。

我认为事先分析整个数据集是最佳解决方案的关键，但它似乎并不容易实现。