Algorithm to make the fewest call to an API

Question

In my program I will have multiple array with about 40 000 strings each with different length (from 10 to 5000 character), I need to send this array to an API wich only accept 5 000 character at a time.

In order to make the fewest API call I need to find the best combinations of string to send each time.

For example if I got an array with different lenght {3, 5, 10, 3, 4, 1, 4} and the maximum lenght of the api is 10. It should returns {10}, {4 1 5}, {3 3 4}.

I've been looking through different algorithm but no one seems to fill my need. (Subset Sum and others)

Any help is greatly appreciated!

Answer 1

Your problem is Bin Packing problem. Please find pretty nice solution in following paper: A new algorithm for optimal bin packing by Richard Korf (see example problem there)

Let us see the example for array:

MAXSIZE=20
[1 2 4 5 7 10 11]

With algorithm from referenced paper you will get:

[11 4 5] [10 7 2 1]

In short this algorithm build bin by:

1. insert into bin maximal element

2. Search for all elements that fits to volume left and maximize their sum

For example in our case first step would be:

# Take max element
[11]
# We have 9 volume left
# All smaller are [1 2 4 5 7] - greedy would take 7 in this case
# 4 and 5 sums up to 9 which is best fit in this case so first bin become:
[11 5 4]
# Next step: take max
[10]
# we have 10 volume left. elements lower than 10:
# [1 2 7]
# this sums up to 10 in this case giving second bin
[10 7 2 1]

And just some example of greedy vs mentioned one:

ARR = [3, 3, 5, 5, 5, 5, 14]
BINSIZE = 20
Greedy result:
Size 3:
[[14, 5], [5, 5, 5, 3], [3]]
Mentioned alg result (size 2):
[[14, 3, 3], [5, 5, 5, 5]]

Also you may be interested in section 'Exact algorithm' on wiki page.