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

Question

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

它应该看起来像，
前提条件:数据中某数的总和<= m，其中m为显式数，
expect:这些数据分成最小计数组。

是否有算法或好主意？

谢谢。

这是一个例子。

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 提到的 bin-packaging 问题。我认为只有这个更容易。

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

Answer 1

看来您的问题与装箱问题非常相似。目标是将各种大小的元素打包到尽可能少的容器中，每个容器都有一些固定容量。一般的方法是使用贪心算法反复尝试将最大的元素打包到它将适合的第一个容器中(首次拟合)，或者尝试将最大的元素放入剩余空间最少的容器中(最合适)。这些都不能保证最优解，但通常会产生接近最优的结果，这可能就足够了。