Partition Problem

Input: An arrangement S of nonnegative numbers {s1, … , sn} and an integer k.
Output: Partition S into k or fewer ranges, to minimize the maximum sum over all the ranges, without reordering any of the numbers.

Where can we place this last divider?

Between the ith and (i + 1)st elements for some i, where 1 ≤ i ≤ n. What is the cost of this? The total cost will be the larger
of two quantities—(1) the cost of the last partition $\sum_{j=i+1}^{n} s_j$ , and (2) the cost of the largest partition formed to the left of i. What is the size of this left partition? is a smaller instance of the same problem

Therefore, let us define M[n, k] to be the minimum possible cost over all partitionings of {s1, … , sn} into k ranges, where the cost of a partition is the largest
sum of elements in one of its parts. Thus defined, this function can be evaluated:

M[n, k] = $\min\limits_{i=1}^{n} max(M[i, k-1], \sum\limits_{j=i+1}^{n} s_j)$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License