最小化組，其中族元素的總和低於一定值

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。