Algorithm for smallest API call

Question

In my program, I will have several arrays with approximately 40,000 lines each with different lengths (from 10 to 5000 characters), I need to send this array to the API, which takes only 5,000 characters at a time.

To make the smallest API call, I need to find the best string combinations to send each time.

For example, if I get an array with different lengths {3, 5, 10, 3, 4, 1, 4}, and the maximum length api is 10. It should return {10}, {4 1 5}, {3 3 4} .

I looked through different algorithms, but no one seemed to fill my need. (Sum of subsets and others)

Any help is much appreciated!

Answer 1

Your problem. Bin packaging problem . Please find a pretty nice solution in the next article: Richard Corf's new algorithm for optimal bin packing (see an example of the problem there)

Let's see an example of an array:

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

Using the reference paper algorithm, you will receive:

 [11 4 5] [10 7 2 1] 

In short, this algorithm builds bin:

• Paste in max bin element

• Find all the items that match the volume on the left and maximize their total.

For example, in our case, the first step will 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 one example of a greedy versus 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]] 

You might also be interested in the Precise Algorithm section of the wiki page.

Answer 2

Definitely looks like a dynamic programming problem. Your question is similar to the Subset Sum problem, except that instead of just finding if such a subset exists, you want to return all such subsets.

This link seems to be close to what you need: http://www.careercup.com/question?id=12899672

Dynamic programming is often quite difficult to wrap around you. I hope someone else will provide a detailed explanation (for me as well), but hopefully this will give you the opportunity to start.

Answer 3

This is a dynamic programming problem (a problem of the sum of a subset) with a change. We not only want to find if the sum exists, but we also want to find all the different subsets.

We are building a two-dimensional logical search table sum (rows) - vs - number (cols), which is typical for many DP problems. To find the subsets that exactly match the sum, we can call the following backtracking function in the lookup table to find the possible real amounts.

 bool backtrack(bool **subset, int sum, int a[], int n) { if(sum == 0) { // Sum possible return true; } if(sum < 0) { //Sum not possible return false; } for(int j=1; j<=n; j++) { if(subset[sum][j] == true) { int val = a[j-1]; // If val is included, can we have a valid sum? bool valid = backtrack(subset, sum-val, a, j-1); if(valid == true) { printf("%d ", val); return true; } } } return false; } 

We can call the above function in such a way as to print a combination of numbers, one combination in each line -

 for(j=1; j<=n; j++) { if(subset[sum][j] == 1) { //For every col which is =1 for the sum'th row bool valid = backtrack(subset, sum-a[j-1], a, j-1); if(valid) { printf("%d\n", a[j-1]); } } } 

Answer 4

How does it work for you? Obviously, you can change max to be what you want, and probably change it to be set from the calling function, but I will leave these options to you.

This worked for me, let me know if you have any problems.

 List<List<string>> Chunk(List<string> inputStrings) { List<List<string>> retVal = new List<List<string>>(); List<string> sortedStrings = inputStrings.OrderByDescending(s => s.Length).ToList(); while (sortedStrings.Any()) { List<string> set = new List<string>(); int max = 10; for (int i = 0; i < sortedStrings.Count(); ++i) { if (max == 0) break; if (max - sortedStrings[i].Length < 0) continue; set.Add(sortedStrings[i]); max -= sortedStrings[i].Length; sortedStrings.RemoveAt(i); --i; } if(set.Any()) retVal.Add(set); } return retVal; } 

Note. It with#. If necessary, I can remake it in another language or with different data structures.

Answer 5

This seems to be allowed by the Greedy algorithm, not the backtracking algorithm that must be executed before sending the string to the API.