Question:
I can't figure out how this problem is optimally solved:
There is a "random" set of N numbers from 0 to M. The distribution is approximately exponential: there are more small ones.
They should be scattered among K containers so as to minimize the spread of the sums of numbers in the containers .
I thought it was necessary to find an average to strive for; sort the set and take from the edges. But it is not clear where to stop when I collect the amount in the next container. So, I missed the "golden mean" 5%, is that good, or still try? Obviously, it is not optimal to take it at random.
Upd. probably not the easiest task. It looks like a one-dimensional " packing problem " + combinatorics.
Answer:
Which immediately comes to mind (but he doesn't seem to be that good).
Start spreading with large numbers and scattering into the smallest cell. Smaller values will trim inequality.
Update
I don't understand why it is hard to take the largest + the smallest? We sort in descending order, for example, we got [5 4 3 3 2 2 1 1 1] . And you need to split it into 3 containers:
- 5 = 4 = 3 // took the 3 largest: 5,4,3
- 5 = 4 = 6 // number 3
- 5 = 6 = 6 // number 2
- 7 = 6 = 6 // number 2
- 7 = 7 = 7 // two numbers 1, 1
- 8 = 7 = 7 // last number 1
I consider this method to be the simplest, but, unfortunately, there are cases when the spread will be imperfect.