我在互联网上发现了以下问题,想知道我将如何解决它:
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.*
请帮忙,看起来很有趣的问题......我实际上花了很多时间,但没有看到任何解决方案......
最佳答案
让我们尝试使用动态规划来解决这个问题。
注意:如果 k > n,我们只能使用 n 区间。
考虑 d[ i ][ j ] 是当 S = {s1 时问题的解>, ..., si } 和 k = j。所以很容易看出:
- d[ 0 ][ j ] = 0 对于从 1 到 k 的每个 j
- d[ i ][ 1 ] = sum(s1...si) 对于每个 i 从 1 到 n
- d[ i ][ j ] = minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)) 对于 i = 1 到 n 和 j = 2 到 k
现在让我们看看为什么会这样:
- 当序列中没有元素时,显然只能有一个区间(一个空区间)并且其元素之和为 0。这就是为什么 d[ 0 ][ j ] = 0 对于从 1 到 k 的所有 j。
- 当只有一个区间时,显然解是序列所有元素的和。所以d[ i ][ 1 ] = sum(s1...si)。
- 现在让我们考虑序列中有i个元素,间隔数是j,我们可以假设最后一个间隔是(si - t + 1...si) 其中 t 是不大于 i 的正整数,所以在这种情况下解是 max ( d[i - t][j - 1], sum(si - t + 1...si), 但作为我们希望解决方案是最小的,我们应该选择 t 来最小化它,所以我们将得到 minfor t = 1 to i (max ( d[i - t][j - 1], sum(si - t + 1...si)).
示例:
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;
}
关于algorithm - 卡在一个面试问题中……数组的分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6454598/