我有几个号码。我需要将它们分成几组，以便一组中所有数字的总和介于预定义的最小值和最大值之间。重点是尽可能少地保留未分组的数字。
Input:
min, max: range for sum of numbers
N1, N2, N3 ... Ni: numbers to group
Output:
[N1,N3,N5],[Ni,Nj,Nk,Nm...]...: groups where sum of numbers is between min and max
Na,Nb,Nc...: numbers, left ingrouped.
最佳答案
这个问题可以看作是装箱到大小为 max 的箱子中，其目标很有趣:最小化未装进容量至少为 min 的箱子中的元素数量。装箱文献中的一个想法是“小”元素(在这种情况下，相对于 max - min 较小的元素)很容易装箱，但对大部分组合爆炸负责的可能性。因此，一些用于装箱的近似算法对大元素做了一些巧妙的处理，然后用小元素填充。减少可能性数量的另一种方法是将数字四舍五入以属于较小的集合。对于装箱(四舍五入)如何做到这一点有些明显，但不清楚如何解决这个问题。
好的，我将举例说明如何将这些想法实例化。假设最大值 = 1 且最小值 = 1/2。当 max = 2 和 min = 1/2 时，让我们尝试找到一个与最优解有竞争力的解。 (这听起来可能很糟糕，但文献中有时会使用这种将 OPT 保持在更高标准的近似保证。)
第一轮每件商品的尺寸最大为 2 的幂。无法包装尺寸为 4 或更大的超大商品。尺寸为 2 或 1 或 1/2 的大件元素有自己的垃圾箱。尺寸为 1/4 或更小的小元素按以下方式处理。每当大小为 1/4 或更小的两个项目具有相同的大小时，将它们合并为一个 super 项目。将所有尺寸为 1/2 的新元素装入它们自己的箱子中。其余的总大小小于 1/2。如果另一个垃圾箱有空间，请将它们放在那里。否则，给他们自己的垃圾箱。
max = 2 的结果解决方案的质量至少与 max = 1 的 OPT 质量一样好。采用 max = 1 的最佳解决方案并四舍五入项目大小。 bad bins 的集合保持不变，因为没有项目更小，并且每个 bin 存储少于 2，因为每个项目都小于以前的两倍。现在足以证明我为 2 的幂给出的打包算法是最优的。我会把它留作练习。
我不希望这立即概括为一个完整的算法。我必须回去工作，但我会采取的方法是强制 OPT 处理 max = 1，同时ALG 开始使用 max = 1 + epsilon，在舍入步骤中用 (1 + epsilon) 的幂代替 2 的幂，然后弄清楚如何打包小项目，可能使用动态程序，因为贪婪可能不起作用.
关于对值列表进行最佳分组的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6817132/