Search code examples
algorithmmathinteger-partition

Divide an integer evenly with a maximum

I need an algorithm for the following:

  • I'm given a specified target sum n, and a specified limit m. These are both positive integers.
  • I want to find an integer partition of the target sum n that has as few summands as possible.
  • Each summand must be less than or equal to the limit m.
  • Within the above constraints, the summands should be as close together as possible; that is, I want n to be partitioned as evenly as possible.

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.