我有一个长度为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)更差。
提前谢谢你。
发布于 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
发布于 2013-01-02 20:35:00
我想知道下面的方法是否可行:
从左边开始,只要sum > sigma
,分支成两个,一个包含推送它的值,另一个不包含推送它的值,用rightSum = totalSum-leftSum
和rightP = 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-1
、sum = 60-12
和sum = 60-19
处理7 6 3 3 3 4 3 4 4 4 3 3 1
和6 3 3 3 4 3 4 4 4 3 3 1
。
我认为这会导致O(P*n)。
当1或2个值是目前为止最大的值时,这可能是一个问题,但是,对于任何值>= sigma,我们可能只需要将其放在它自己的分区中(对数组进行预处理以找到这些值可能是最好的想法(并适当地减少sum ))。
如果它有效,它应该有望最小化平方和误差(或接近平方误差),这似乎是理想的衡量标准。
发布于 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从第一个版本}
https://stackoverflow.com/questions/14120729
复制相似问题