java - 是否有一种有效的算法可以将几组数字打包到几个桶中？

Question

例如，您有多个double列表，您需要将它们分布在几个固定大小的“桶”中(桶大小也是一个double)。还有两个额外的约束:

• 某些列表中的值只能进入某些(预先指定的)桶:

  bucket1 <-\
             |--- list1
            /
           /
  bucket2 <--\
  bucket3 <---- list2
  bucket4 <--/
  
  bucket5 <--- list3
  

• 生成的分布必须尽可能均匀(以便所有桶的负载因子都为 0.5)。

此类问题的具体示例:想象一下，如果您有多个电源单元(“桶”)和几 block 灯板。每个供电单元连接到一 block 或几 block 板上，每个供电单元的容量不同，灯消耗的能量也不同。如果一些电路板连接到多个电源单元，那么您可以将一些灯“分配”到第一个电源，一些灯“分配”到第二个，等等。

对于大量元素，使用暴力很快变得不可行。

有没有有效的方法？

编辑: 我设计了以下方法 - 它似乎很快就能收敛到所需的结果。思路如下:

• 首先，对于每个列表，我使用最小负载桶启发式将项目分配到允许的桶中。
• 然后，我执行以下操作:
  • 对于每个列表:
    • 从桶中取出列表对应的item
    • 再次分发它们，使用相同的最小负载启发式
    • 计算最大负载桶大小与最小负载大小的比率(对于允许的桶)
  • 如果比率小于某个常数(我采用了 1.02)，或者如果传递的步骤太多，则终止循环。

一般的想法是“平滑”桶，直到分布变得足够平坦，这通常意味着我们达到了所需的目标。

这是一个好的算法吗？

Answer 1

对我来说听起来像 bin packing problem或带有附加约束的背包问题(某些列表只能转到特定的桶)，您需要一个解决方案将所有桶填充到至少一个特定的负载因子。说到“高效”，我会说你所描述的应该是 NP 难的(“应该”是因为我还没有时间考虑从 NP 问题减少到你的具体问题，但我很确定有一个)。

你可以尝试什么:首先解决约束问题并确定哪些行可以进入哪些桶，然后贪婪地填充桶。如果您的约束很严格，您可以进行回溯。