陷入面试问题..阵列的分区

Question

我在互联网上发现了以下问题，想知道如何解决：

问题：没有重排的整数分区

输入：非负数的排列S｛S₁。，s_n}和整数k。

输出：将S划分为k个或更少的范围，以最小化最大值在所有k个或更少范围的和中，而不重新排序数字。*

请帮忙，这似乎是一个有趣的问题。。。事实上，我花了很多时间，但没有找到任何解决方案。。

Answer 1

让我们尝试使用动态编程来解决这个问题。

注意：如果k>n，我们只能使用n区间

让我们考虑d[i][j]是当S={S₁，…，S_i}和k=j时问题的解。所以很容易看出：

1. d[0][j]=0对于从1到k的每个j
2. d[i][1]=从1到n的每个i的总和（s₁…s_i）
3. d[i][j]=min_{对于t=1到i}（max（d[i-t][j-1]，sum（s_i-t+1…s_i））对于i=1到n和j=2到k

现在让我们看看为什么这样做：

1. 当序列中没有元素时，很明显只能有一个区间（空区间），其元素之和为0。这就是为什么对于从1到k的所有j，d[0][j]=0
2. 当只有一个区间时，很明显，解是序列中所有元素的和。所以d[i][1]=sum（s₁…s_i）
3. 现在让我们考虑序列中有i元素，区间的数量是j，我们可以假设最后一个区间是（s_i-t+1…s_i），其中t是不大于i-的正整数，所以在这种情况下，解是max（d[i-t][j-1]，sum，但由于我们希望解是最小的，我们应该选择t以使其最小化，因此对于t=1到i，我们将得到min_{（max（d[i-t][j-1]，sum（si-t+1…si/li>}

示例：

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

代码：

#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

这个问题取自Steven Skiena的书《算法设计手册》。你可以在谷歌图书上阅读详细的讨论和他的解决方案。更好的是，买这本书。