algorithmmathinteger-partition

Divide an integer evenly with a maximum


I need an algorithm for the following:

So, for example, if the target sum is n = 80 and each summand must be at most m = 30, then I need at least three summands, and the most even partition is 26 + 27 + 27.

How would I compute that?


Solution

  • First, you get the size of the array with the following formula using integer division:

    size = (variable + maximum - 1) / maximum
    

    Next you fill the array with the following formulas:

    extra = variable % size;
    value = variable / size;
    for each array value, set to value + 1 as long as there's extra; 
        value when the extra goes to zero.