algorithm - 如何将数据分成最小组

Question

我想知道是否有一种算法可以将一些数据分成最小组。

它应该看起来像，
前提条件：一些数据的总和 <= m，其中 m 是一个明确的数字，
期望：这些数据分成最小计数组。

有算法或好主意吗？

谢谢。

这是一个例子。

List<Integer> rawList = Arrays.asList(1, 1, 1, 2, 10, 5, 8, 3);

您可以将它们分成 8 个组，每个组包含 1 个数字，
这不是我想要的。

Integer maxSum = 12; //Assume that one group can holds max sum of 12.

我需要最少的组，所以答案看起来像

List<Integer> group1 = Arrays.asList(10, 2);
List<Integer> group2 = Arrays.asList(8, 3, 1);
List<Integer> group3 = Arrays.asList(5, 1, 1);

上面的例子只用了 3 组来拆分原始数据。
这 3 个组将是一个答案。（还有其他方法可以使用最小组。）

这似乎类似于@Dillon Davis 提到的装箱问题。我认为只有这一个更容易。

附言。答案需要最小组，时间和空间复杂度不是主要问题。

标签： algorithm

Answer 1

看来您的问题与装箱问题非常相似。目标是将各种尺寸的元素打包到尽可能少的箱子中，每个箱子都有固定的容量。一般的方法是使用贪心算法重复尝试将最大元素打包到它将适合的第一个 bin 中（first-fit），或者尝试将最大元素放入 bin 中并尽可能少的剩余空间（最合适）。这些都不能保证最佳解决方案，但通常会产生接近最佳的结果，这可能就足够了。