CODEWITHSUNDEEP
algorithmdynamic-programming
AGeek
AGeek

Reputation: 5225

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

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 {s1, . . . , sn} 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..

Upvotes: 16

Views: 6738

Answers (2)

Mihran Hovsepyan
Mihran Hovsepyan

Reputation: 11108

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 = {s1, ..., si } 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(s1...si) for each i from 1 to n
  3. d[ i ][ j ] = minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)) 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(s1...si).
  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 (si - t + 1...si) where t is positive integer not greater than i, so in that case solution is max ( d[i - t][j - 1], sum(si - t + 1...si), but as we want the solution be minimal we should chose t such to minimize it, so we will get minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)).

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;
}

Upvotes: 21

NPE
NPE

Reputation: 500923

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.

Upvotes: 8

Related Questions