ruby - 将数组划分为权重相等的子数组

Question

这里是算法题。

我有一个包含产品重量的无序数组，例如[3, 2, 5, 5, 8] 需要分成更小的数组。

规则:

• 必需:应返回 1 个或多个数组。
• 要求:数组的总和不应超过 12。
• 必需:返回数组的最小可能数量，例如。上面例子的总权重是23，可以装进两个数组。
• 理想:数组的权重应尽可能均匀。

在上面的例子中，理想的返回是[ [3, 8], [2, 5, 5] ]

我目前的想法:

• 要返回的数组数量将为 (sum(input_array)/12).ceil
• A greedy algorithm可以很好地工作吗？

Answer 1

这是 bin packing problem 的组合和 multiprocessor scheduling problem .两者都是 NP-hard。

您的三个要求构成了装箱问题:找到适合所有数字的固定大小 (12) 的最小箱数。

一旦你解决了这个问题，你就会遇到多处理器调度问题:给定固定数量的箱子，在它们之间分配数量的最均匀方式是什么。

这两个问题都有许多著名的近似算法。