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

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] 

这显然是更好的partiton作为

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

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