Minimize number of groups, where sum of group elements is below certain value

Question

Let's say I have a list of 10 items and a max_sum:

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

I want to group the elements in items, and I want to find the minimum number of groups, provided that the sum of elements in each group is less than a pre-set value, max_sum, where all elements of items are less than max_sum.

General idea for algorithm:

• initialize 1) empty list new_group, 2) float space_left in group =(max_sum - sum(new_group))
• find largest item, such that item <= space_left
• append largest item to new_group
• update space_left
• remove item from items
• once min(items) > space_left, start over
• count cycles to find minimum number of groups

So for the values given, this algorithm would yield 4 groups:

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

I think my above approach will work but am wondering if there is a more direct/better way. Thanks!

Answer 1

Your approach will not work. You use a greedy algorithm that may lead to unused space in some groups. E.g.:

 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]

Here it would obviously be better to partiton as

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

As noted in a comment, this is the well-known bin packing problem. If you want even further reading, you can have a look at Wikipedia in addition to the link provided in the comment.