数组坚持一个面试问题...分区 [英] 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:

问题：整数分区不重排

输入：的非负数的安排小号{S <子> 1 。 。 。   ，S <子> N }和一个整数k。

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

输出：划分S为k个或更少的范围内，以最大限度减少   所有的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..

推荐答案

让我们尝试用动态规划来解决这个问题。

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

注意：如果的 K> N 的，我们只能使用的 N 的间隔

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

让考虑的 D [I] [J] 的是这个问题的解决方案时的取值的= {取值<子> 1 ... 取值<子>我 的}和 K = Ĵ的。所以很容易看到的是：

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 的每一个的Ĵ的距离的 1 的到的 K 的
2. 的 D [I] [1] = SUM（S <子> 1 内容S <子>我）的每一个的我的 1 的到的 N 的
3. 的 D [I] [J] =分钟<子>为T = 1到i （MAX（D [我 - T] [J - 1，总和（S <子>我 - T + 1 内容S <子>我）），其中i = 1到n和j = 2至K 的

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

现在让我们来看看为什么这个作品：

1. 当有该序列很显然，只有一个间隔可以有（空的）其元素和总和在没有任何元素是0。这就是为什么的 D [0] [j]的= 0 所有的Ĵ的距离的 1 的到的 K 的
2. 当只有一个间隔可以存在，很显然，溶液是序列中的所有元素的总和。因此， D [I] [1] = SUM（S <子> 1 内容S <子>我）的
3. 现在，让我们来看看还有的我的顺序和时间间隔的数量元素的Ĵ的，我们可以假设，最后一个区间是（S <子>我 - T + 1 内容S <子>我）其中的 T 的是正整数不超过的我的，所以在这种情况下，解决办法是 MAX（D [我 - T] [J - 1，总和（S <子>我 - T + 1 内容S <子>我）的，但作为我们希望该解决方案是最小的，我们应该选择的 T 的这种最小化，所以我们会得到的分<子>为T = 1到i （MAX（D [我 - T] [J - 1，总和。（S <子>我 - T + 1 内容S <子>我））的

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)).

示例：

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

这篇关于数组坚持一个面试问题...分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！