最小化组数，其中组元素的总和低于特定值

Question

假设我有10个项目的清单和一个max_sum：

items = [1, 2, 4, 4, 10, 10, 15, 18, 21, 22]
max_sum = 30

我想对中的元素进行分组items，并且要找到最小的组数，前提是每组中的元素总数小于预设值max_sum，其中的所有元素items均小于max_sum。

算法的一般思路：

• 初始化1）空列表new_group，2）space_left在组中浮动=(max_sum - sum(new_group))
• 查找最大的项目，使项目<= space_left
• 将最大的项目附加到 new_group
• 更新 space_left
• 从中删除项目 items
• 一旦min(items)> space_left，重新开始
• 计算周期以找到最小组数

因此，对于给定的值，此算法将产生4组：

[22, 4, 4]
[21, 2, 1]
[18, 10]
[15, 10]

我认为我的上述方法会奏效，但我想知道是否有更直接/更好的方法。谢谢！

Answer 1

你的方法不会起作用。您使用贪婪算法可能会导致某些组中出现未使用的空间。例如：

 items = [13, 11, 10, 10, 9, 7]
 max_sum = 30

 First group  => [13, 11] (leaving a diff of 6)
 Second group => [10, 10, 9] (leaving a diff of 1)
 Third group  => [7]

在这里显然更好地划分为

First group  => [13, 10, 7]
Second group => [11, 10, 9]

正如评论中指出的，这是众所周知的装箱问题。如果您想进一步阅读，除了评论中提供的链接之外，您还可以查看维基百科。