将数组划分为k个连续分区，使得最大分区之和最小
将数组划分为k个连续分区，使得最大分区之和最小
提问于 2016-09-24 15:47:32
这里，最大和子集是给出最大和的k个子集之一，例如: arr = 10,5,3,7和k=2在k个子集中划分arr的可能方法是
{10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7}和
{[10,5],[3,7} is the optimal one.回答 2
Stack Overflow用户
发布于 2018-11-11 09:04:03
你可以在这里找到一篇关于基于动态编程的解决方案的好文章：https://www.geeksforgeeks.org/painters-partition-problem/，它的复杂度是O(k*N^2)。
要获得更好的解决方案，您可以按照其他人的建议使用二进制搜索方法。你可以在这里找到一个使用二进制搜索的更详细的解决方案：https://www.geeksforgeeks.org/painters-partition-problem-set-2/，它的复杂度是O(NlogN)
Stack Overflow用户
发布于 2016-09-24 18:06:29
这种划分只是一个蛮力问题。你必须专注于要最小化的函数。所以你必须最小化与平均值的偏差。
int sum_arr(int *arr,int size)
{
int res=0;
while (size-->0)
res+=*arr++;
return res;
}
int minimize( const int *array, int size)
{
int i,j,cur_i;
double dev, cur_min,avg=(double)sum_arr(array,size)/size;
for (i=1;i<size-1;i++)
{
dev=abs(avg-sum_arr(array,i));
dev+=abs(avg-sum_arr(array+i,size-i);
if (dev<cur_min)
{
cur_min=dev;
cur_i=i;
}
}
return cur_i;
}一个简单的代码是：(未测试)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39673898
复制相关文章
相似问题