首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >将一个数组分成P个平衡和子数组的算法

将一个数组分成P个平衡和子数组的算法
EN

Stack Overflow用户
提问于 2013-01-02 18:50:14
回答 5查看 9.9K关注 0票数 26

我有一个长度为N的大数组,让我们这样说:

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

我需要将此数组拆分为P个子数组(在本例中,P=4将是合理的),以便每个子数组中的元素之和尽可能接近sigma,即:

sigma=(sum of all elements in original array)/P

在本例中,为sigma=15

为了清楚起见,一种可能的结果是:

2 4 6    7 6 3 3   3 4 3 4    4 4 3 3 1
(sums: 12,19,14,15)

我已经写了一个非常天真的算法,基于我如何手工做除法,但我不知道如何强加一个条件,即和为(14,14,14,14,19)的除法比(15,14,16,14,16)更差。

提前谢谢你。

EN

回答 5

Stack Overflow用户

发布于 2013-01-02 22:48:53

工作代码如下(我使用的是php语言)。这个代码决定了零件的数量;

$main = array(2,4,6,1,6,3,2,3,4,3,4,1,4,7,3,1,2,1,3,4,1,7,2,4,1,2,3,1,1,1,1,4,5,7,8,9,8,0);
$pa=0;
for($i=0;$i < count($main); $i++){
$p[]= $main[$i];
if(abs(15 - array_sum($p)) < abs(15 - (array_sum($p)+$main[$i+1])))
{
$pa=$pa+1;
$pi[] = $i+1;
$pc =  count($pi);

$ba = $pi[$pc-2] ;

$part[$pa] = array_slice( $main,  $ba, count($p));
unset($p);
}
}
print_r($part);
for($s=1;$s<count($part);$s++){
echo '<br>';
echo array_sum($part[$s]);
}

代码将输出部分和,如下所示

13
14
16
14
15
15
17
票数 1
EN

Stack Overflow用户

发布于 2013-01-02 20:35:00

我想知道下面的方法是否可行:

从左边开始,只要sum > sigma,分支成两个,一个包含推送它的值,另一个不包含推送它的值,用rightSum = totalSum-leftSumrightP = P-1递归处理右边的数据。

因此,一开始,sum = 60

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

然后对于2 4 6 7,sum = 19 > sigma,因此拆分为:

2 4 6     7 6 3 3 3 4 3 4 4 4 3 3 1

2 4 6 7     6 3 3 3 4 3 4 4 4 3 3 1

然后分别用P = 4-1sum = 60-12sum = 60-19处理7 6 3 3 3 4 3 4 4 4 3 3 16 3 3 3 4 3 4 4 4 3 3 1

我认为这会导致O(P*n)。

当1或2个值是目前为止最大的值时,这可能是一个问题,但是,对于任何值>= sigma,我们可能只需要将其放在它自己的分区中(对数组进行预处理以找到这些值可能是最好的想法(并适当地减少sum ))。

如果它有效,它应该有望最小化平方和误差(或接近平方误差),这似乎是理想的衡量标准。

票数 0
EN

Stack Overflow用户

发布于 2013-01-02 20:49:04

提出了一种基于回溯的算法。选择的main函数从原始数组中随机选择一个元素,并将其添加到分区的数组中。对于每个添加,都将检查以获得比原始解决方案更好的解决方案。这将通过使用计算偏差的函数来实现,以区分每个添加到页面的新元素。无论如何,我认为在循环中添加一个原始变量是很好的,因为你不能达到想要的解决方案,这将迫使程序结束。通过所需的解决方案,我的意思是添加与if中的条件施加的条件相关的所有元素。

sum=CalculateSum(vector)
Read P
sigma=sum/P
initialize P vectors, with names vector_partition[i], i=1..P
list_vector initialize a list what pointed this P vectors
initialize a diferences_vector with dimension of P
//that can easy visualize like a vector of vectors
//construct a non-recursive backtracking algorithm
function Deviation(vector) //function for calculate deviation of elements from a vector
{
  dev=0
  for i=0 to Size(vector)-1 do
  dev+=|vector[i+1]-vector[i]|
  return dev 
}
iteration=0
//fix some maximum number of iteration for while loop
Read max_iteration
//as the number of iterations will be higher the more it will get  
//a more accurate solution
while(!IsEmpty(vector))
{   
   for i=1 to Size(list_vector) do
   {
       if(IsEmpty(vector)) break from while loop
       initial_deviation=Deviation(list_vector[i])
       el=SelectElement(vector) //you can implement that function using a randomized   
                               //choice of element
       difference_vector[i]=|sigma-CalculateSum(list_vector[i])|
       PutOnBackVector(vector_list[i], el)
       if(initial_deviation>Deviation(difference_vector))
          ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector)
    }
    iteration++
    //prevent to enter in some infinite loop
   if (iteration>max_iteration) break from while loop    

}如果某些代码增加了计算出的偏差量,您可以通过先添加一些代码来改变这一点。aditional_amount=0 iteration=0 while { ...if(initial_deviation>Deviation(difference_vector)+additional_amount) ExtractFromBackVectorAndPutOnSecondVector(list_vector,向量) if(iteration>max_iteration) { iteration=0 aditional_amout+=1/some_constant } iteration++ //删除第二个if从第一个版本}

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14120729

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档