Recently I got into a very (basic) problem. My feeling is that it must have a very theoretical solution which I am not aware of. The problem statement is this:
Let [x_1, x_2, ..., x_n] is a list of positive integers. I need to make the minimum split of these numbers such that sum of those numbers in each split should not exceed N.
For example: The list is [67, 56, 12345, 555555, 555555, 555555] and N=1000000, then the one minimum splits would be [[555555, 12345, 67, 56], [555555], [555555]].
One solution I thought is like this:
- sort the list.
- Take max value and add minimum values one by one so that the some do not exceed N.
- Remove elements used in 2 from the list and try 2 and 3 again on the modified list until the list exhaust.
The problem is that I am not sure it will provide the minimum split.
Thanks for any solution.