Stuck with an interview Question... Partitioning of an Array

Question

I found the following problem on the internet, and would like to know how I would go about solving it:

Problem: Integer Partition without Rearrangement

Input: An arrangement S of non negative numbers {s₁, . . . , s_n} and an integer k.

Output: Partition S into k or fewer ranges, to minimize the maximum of the sums of all k or fewer ranges, without reordering any of the numbers.*

Please help, seems like interesting question... I actually spend quite a lot time in it, but failed to see any solution..

Answer 1

Let's try to solve the problem using dynamic programming.

Note: If k > n we can use only n intervals.

Let consider d[ i ][ j ] is solution of the problem when S = {s₁, ..., s_i } and k = j. So it is easy to see that:

1. d[ 0 ][ j ] = 0 for each j from 1 to k
2. d[ i ][ 1 ] = sum(s₁...s_i) for each i from 1 to n
3. d[ i ][ j ] = min_{for t = 1 to i} (max ( d[i - t][j - 1], sum(s_{i - t + 1}...s_i)) for i = 1 to n and j = 2 to k

Now let's see why this works:

1. When there is no elements in the sequence it is clear that only one interval there can be (an empty one) and sum of its elements is 0. That's why d[ 0 ][ j ] = 0 for all j from 1 to k.
2. When only one interval there can be, it is clear that solution is sum of all elements of the sequence. So d[ i ][ 1 ] = sum(s₁...s_i).
3. Now let's consider there are i elements in the sequence and number of intervals is j, we can assume that last interval is (s_{i - t + 1}...s_i) where t is positive integer not greater than i, so in that case solution is max ( d[i - t][j - 1], sum(s_{i - t + 1}...s_i), but as we want the solution be minimal we should chose t such to minimize it, so we will get min_{for t = 1 to i} (max ( d[i - t][j - 1], sum(s_{i - t + 1}...s_i)).

Example:

S = (5,4,1,12), k = 2

d[0][1] = 0, d[0][2] = 0

d[1][1] = 5, d[1][2] = 5

d[2][1] = 9, d[2][2] = 5

d[3][1] = 10, d[3][2] = 5

d[4][1] = 22, d[4][2] = 12

Code:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main ()
{
    int n;
    const int INF = 2 * 1000 * 1000 * 1000;
    cin >> n;
    vector<int> s(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    vector<int> first_sum(n + 1, 0);
    for(int i = 1; i <= n; ++i)
        first_sum[i] = first_sum[i - 1] + s[i];
    int k;
    cin >> k;
    vector<vector<int> > d(n + 1);
    for(int i = 0; i <= n; ++i)
        d[i].resize(k + 1);
    //point 1
    for(int j = 0; j <= k; ++j)
        d[0][j] = 0;
    //point 2
    for(int i = 1; i <= n; ++i)
        d[i][1] = d[i - 1][1] + s[i]; //sum of integers from s[1] to s[i]
    //point 3
    for(int i = 1; i <= n; ++i)
        for(int j = 2; j <= k; ++j)
        {
            d[i][j] = INF;
            for(int t = 1; t <= i; ++t)
                d[i][j] = min(d[i][j], max(d[i - t][j - 1], first_sum[i] - first_sum[i - t]));
        }


    cout << d[n][k] << endl;
    return 0;
}

Answer 2

This problem is taken verbatim from Steven Skiena's book "The Algorithm Design Manual". You can read the detailed discussion and his solution on Google Books. Better yet, buy the book.