将数组划分为K个子数组，差异最小 [英] Partition an array into K subarrays with minimal difference
问题描述
免责声明:
描述的问题看起来像是比赛中的任务.我没有参加任何比赛，也没有任何正在进行的比赛，可能涉及到这个问题.如果有任何一个，我将结束问题以保持公平！
Described problem looks like a task from a competition. I'm not participating in any of them, I'm not aware about any ongoing competitions, which might involve the problem. If there are any of them, I'll close the question to stay fair!
我有一个问题: 在给定值数组A和整数K的情况下，将A拆分为正好K个不重叠的连续子数组，以使子数组的和与最小值之和与子数组的最大值之差最小.可以将A沿任意方向旋转任意数量.
I have a problem: given an array A of values and integer K, split A into exactly K non-overlapping contiguous subarrays in such way that difference between a subarray with minimal and a subarray maximum sums is minimal. It is allowed to rotate A by any number in any direction.
考虑一个例子:
输入:A = [5 1 1 1 3 2]，K = 3
Input: A = [5 1 1 1 3 2], K = 3
输出:[5] [1 1 1] [3 2]，最大和= 5，最小和= 3，结果= 2
Output: [5][1 1 1][3 2], maximum sum = 5, minimum sum = 3, result = 2
我有部分正常工作的代码(非常丑陋，我很糟糕，但这并不意味着要提高产品质量):
I have partially working code (terribly ugly, my bad, but it does not meant to be production quality):
#include <climits>
#include <cstdio>
#include <cstring>
const int max_n = 50;
const int max_k = 20;
int deps[max_n];
int max (int x, int y) {
return x > y ? x : y;
}
int min (int x, int y) {
return x < y ? x : y;
}
int sum (int a[], int start, int end) {
int res = 0;
for (int i = start; i <= end; ++i) res += a[i];
return res;
}
int k_partitioning(int k, int n, int deps[]) {
int res = INT_MAX;
// consider all possible rotations/shifts
for(int offset = 0; offset < n; ++offset) {
for(int l_min = 0; l_min < n; ++l_min) {
for(int r_min = l_min; r_min < n; ++r_min) {
// check minimal sum subarray
int min_sum = sum (deps, l_min, r_min);
int dp[k][n];
for (int s = 0; s < k; ++s) {
for (int q = 0; q < n; ++q) {
dp[s][q] = 0;
}
}
// assuming that current sum is a target sum
dp[0][r_min-l_min] = min_sum;
for(int p = 1; p < k; ++p) {
for(int l_max = 0; l_max < n; ++l_max) {
for(int r_max = 0; r_max < n; ++r_max) {
int max_sum = sum(deps, l_max, r_max);
if (max_sum >= min_sum) dp[p][r_max] = max(dp[p-1][l_max], max_sum);
} // l_maxs
} // r_maxs
} // partitions
// printing dp
// skip incorrect partitioning, when not all K partitions were used
if (dp[k-1][n-1] == 0) continue;
// update difference
res = min (res, dp[k-1][n-1] - min_sum);
} // end min sum seg
} // start min sum seg
//break;
} // cuts
return res;
}
int main(int argc, char* argv[]) {
int k = 0;
scanf("%d", &k);
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &deps[i]);
}
printf ("%d\n", k_partitioning(k, n, deps));
return 0;
}
这个想法很简单:假设当前分区具有最小总和，枚举所有可能的最大分区，设置动态编程以生成具有最小值的最大总和，检查差异.总复杂度:O(K * N ^ 4).
The idea is simple: assume that current partition has minimal sum, enumerate all possible maximal partitions, setup dynamic programming for generating maximum sum with minimal value, check for difference. Total complexity: O(K*N^4).
我的问题是它无法通过某些测试，因此无法解决问题.有人可以帮我吗?
My problem is that it fails some tests and I'm stuck with troubleshooting it. Could someone help me with it?
测试失败，例如:
N = 4，K = 2，A = [6 13 10 2]
N = 4, K = 2, A = [6 13 10 2]
更新
此版本应解决以前的一些问题.首先，它消除了偏移"上的浪费循环，并仅在l_min循环的末尾添加了数组旋转.其次，我注意到，dp不能用0初始化-这是最小化任务，因此应使用较大的值进行初始化(取决于问题的常量，此处的max_value已经超出了值域).最后，间隔不应再重叠-每个和都排除间隔的左端.但是，它仍然无法产生预期的结果.
This version should fix some previous issues. First, it removes wasteful loop over "offsets" and adds just an array rotation in the end of l_min loop. Second, I've noticed, that dp can't be initialized with 0 - this is minimization task, so it should be initialized with some large value (depends on a problem's constants, max_value here already is out of value domain). Finally, intervals should not overlap anymore - each sum exclude left end of an interval. However, it still does not produce expected results.
#include <climits>
#include <cstdio>
#include <cstring>
const int max_value = 200000;
const int max_n = 50;
const int max_k = 20;
int deps[max_n];
int max (int x, int y) {
return x > y ? x : y;
}
int min (int x, int y) {
return x < y ? x : y;
}
int sum (int a[], int start, int end) {
int res = 0;
for (int i = start; i <= end; ++i) res += a[i];
return res;
}
int k_partitioning(int k, int n, int deps[]) {
int res = max_value;
for(int l_min = 0; l_min < n; ++l_min) {
for(int r_min = l_min; r_min < n; ++r_min) {
int min_sum = sum (deps, l_min+1, r_min);
int dp[k][n];
for (int s = 0; s < k; ++s) {
for (int q = 0; q < n; ++q) {
dp[s][q] = max_value;
}
}
// assuming that current sum is a target sum
dp[0][r_min-l_min] = min_sum;
for(int p = 1; p < k; ++p) {
for(int l_max = 0; l_max < n; ++l_max) {
for(int r_max = l_max; r_max < n; ++r_max) {
int max_sum = sum(deps, l_max+1, r_max);
if (max_sum >= min_sum) dp[p][r_max] = max(dp[p-1][l_max], max_sum);
} // l_maxs
} // r_maxs
} // partitions
// skip incorrect partitioning, when not all K partitions were used
if (dp[k-1][n-1] == max_value) continue;
// update difference
res = min (res, dp[k-1][n-1] - min_sum);
} // end min sum seg
// rotate an array to consider different starting points
int tmp[n];
for (int i = 0; i < n; ++i) {
int new_idx = i + n + 1;
tmp[new_idx % n] = deps[i];
}
for(int i = 0; i < n; ++i) deps[i] = tmp[i];
} // start min sum seg
return res;
}
int main(int argc, char* argv[]) {
int k = 0;
scanf("%d", &k);
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &deps[i]);
}
printf ("%d\n", k_partitioning(k, n, deps));
return 0;
}
推荐答案
好的，我想我做到了！
想法如下:我们假设最小总和间隔始终从0开始.然后，我们开始从最小间隔的右边界开始枚举最大总和间隔.我们针对当前最大间隔构建DP问题，以确定最小最大和.之后，您更新结果并将数组旋转一个.
The idea is following: we assume that minimum sum interval always starts from 0. Then we start to enumerate maximum sum intervals, starting from the right boundary of the minimal interval. We build DP problem for current max interval to determine a minimum maximal sum. After that you update result and rotate an array by one.
我的代码不是完美的，因为我无法计算每次迭代的电流总和.可以预先计算它们，而每次都只对其编制索引.
My code is not perfect in a way that I compute current sums each iteration. One can pre-compute them and just index them each time.
此代码可能有一些错误，但它通过了我的所有测试.
This code might have some bugs, but it passes all test that I have.
#include <climits>
#include <cstdio>
#include <cstring>
const int max_value = 200000;
const int max_n = 50;
const int max_k = 20;
int deps[max_n];
int max (int x, int y) {
return x > y ? x : y;
}
int min (int x, int y) {
return x < y ? x : y;
}
int sum (int a[], int start, int end) {
int res = 0;
for (int i = start; i <= end; ++i) res += a[i];
return res;
}
int k_partitioning(int k, int n, int deps[]) {
int res = max_value;
for(int offset = 0; offset < n; ++offset) {
int l_min = 0;
for(int r_min = l_min; r_min < n; ++r_min) {
int min_sum = sum (deps, l_min, r_min);
int dp[k][n];
for (int s = 0; s < k; ++s) {
for (int q = 0; q < n; ++q) {
dp[s][q] = max_value;
}
}
// assuming that current sum is a target sum
dp[0][r_min-l_min] = min_sum;
for(int p = 1; p < k; ++p) {
for(int l_max = r_min; l_max < n; ++l_max) {
for(int r_max = l_max; r_max < n; ++r_max) {
int max_sum = sum(deps, l_max+1, r_max);
if (max_sum >= min_sum) {
dp[p][r_max] = min(dp[p][r_max], max(dp[p-1][l_max], max_sum));
}
} // l_maxs
} // r_maxs
} // partitions
// skip incorrect partitioning, when not all K partitions were used
if (dp[k-1][n-1] == max_value) continue;
// update difference
res = min (res, dp[k-1][n-1] - min_sum);
} // end min sum seg
int tmp[n];
for (int i = 0; i < n; ++i) {
int new_idx = i + n - 1;
tmp[new_idx % n] = deps[i];
}
for(int i = 0; i < n; ++i) deps[i] = tmp[i];
} // start min sum seg
return res;
}
int main(int argc, char* argv[]) {
int k = 0;
scanf("%d", &k);
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &deps[i]);
}
printf ("%d\n", k_partitioning(k, n, deps));
return 0;
}
这篇关于将数组划分为K个子数组，差异最小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
