我有一个长度为N的大阵，让我们这样说：
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
我需要拆分该阵列为P的子阵列（在该示例中， P=4将是合理），使得在每个子阵列中的元素的总和为尽可能接近西格玛，为：
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）。
先感谢您。
首先，让我们通过指定的输入，输出和每个可能的解决方案（我希望这是你们的利益）衡量正式优化问题：
给定的正整数的数组A和正整数P，该阵列的单独为P不重叠的子阵列使得每个子阵列的总和和所述子阵列的完美总和（总和（A）/ P）之间的差为最小。
输入 ：正整数的阵列A; P为正整数。
输出 ： 表示的每个子阵列，其中这些子阵列的长度之和是等于A的长度的长度P是非负整数的阵列SA。
测量 ：ABS（总和（SA）-sum（A）/ P）是最小的每个SA∈{SA | sa = ( A i , …, A i + SA j ) for i = (Σ SA j ), j from 0 to P -1}. SA =（A 1，...，A 1 + SA j）的对于i =（ΣSA j）的 ，J为0〜P -1}。
输入和输出定义了一套有效的解决方案。 该措施规定的措施比较多的有效解决方案。 而且，由于我们所要寻找的，以完美的解决方案（最小化问题）最不差的解决方案， 措施也应该是最小的。
有了这些信息，这是很容易实现的measure功能（这里在Python）：
def measure(a, sa):
sigma = sum(a)/len(sa)
diff = 0
i = 0
for j in xrange(0, len(sa)):
diff += abs(sum(a[i:i+sa[j]])-sigma)
i += sa[j]
return diff
print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8
现在，找到一个最佳的解决方案是有点困难。
我们可以用回溯算法寻找有效的解决方案，并使用测量功能来评价他们。 基本上，我们尝试P是总结长度（A）来表示所有可能的解决方案，有效的非负整数的所有可能的组合。 虽然这可以确保不会错过任何一个有效的解决方案，它基本上是与我们可以忽略一些分支机构，可以没有任何比我们还没有最好的解决方案更好地造福蛮力的方法。 例如在上面的例子中，我们就不需要测试用的解决方案[9，...]（ 测量 > 38）如果我们已经有≤38与测量的溶液。
继从维基百科的伪模式，我们的bt功能如下所示：
def bt(c):
global P, optimum, optimum_diff
if reject(P,c):
return
if accept(P,c):
print "%r with %d" % (c, measure(P,c))
if measure(P,c) < optimum_diff:
optimum = c
optimum_diff = measure(P,c)
return
s = first(P,c)
while s is not None:
bt(list(s))
s = next(P,s)
全局变量P ， optimum ，和optimum_diff表示问题的实例为保持A，P，和sigma其测量值，以及最优解和：
class MinimalSumOfSubArraySumsProblem:
def __init__(self, a, p):
self.a = a
self.p = p
self.sigma = sum(a)/p
接下来我们指定的reject和accept是相当简单的功能：
def reject(P,c):
return optimum_diff < measure(P,c)
def accept(P,c):
return None not in c
这只是拒绝其措施已经比我们还没有最佳的解决方案更加任何候选人。 而且我们接受任何有效的解决方案。
该measure功能也略有变化，由于这样的事实， c现在可以包含None值：
def measure(P, c):
diff = 0
i = 0
for j in xrange(0, P.p):
if c[j] is None:
break;
diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
i += c[j]
return diff
剩下的两个功能， first和next更复杂一点：
def first(P,c):
t = 0
is_complete = True
for i in xrange(0, len(c)):
if c[i] is None:
if i+1 < len(c):
c[i] = 0
else:
c[i] = len(P.a) - t
is_complete = False
break;
else:
t += c[i]
if is_complete:
return None
return c
def next(P,s):
t = 0
for i in xrange(0, len(s)):
t += s[i]
if i+1 >= len(s) or s[i+1] is None:
if t+1 > len(P.a):
return None
else:
s[i] += 1
return s
基本上， first要么替换下一个None在列表中的值或者0 ，如果它不在列表或其余表示一个有效的解决方案（这里有点优化），如果它在列表中的最后一个值的最后一个值，或将其返回None如果没有None在列表中值。 next只需加一最右边的整数或返回None如果增量将违反总限额。
现在，所有你需要的是创建一个问题实例，初始化的全局变量和调用bt与根：
P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)
如果我不在这里误会，多一个方法是动态规划。
您可以定义P [POS，n]，如最小的可能“惩罚”积攒起来的，如果是生成的N子阵位置POS。 显然，有一些位置pos'，使得
P [POS'，N-1] +罚分（POS'，POS）= P [POS，n]的
你可以只减少了POS' = 1..pos。
天真实施将为O运行（N ^ 2 * M），其中N - 原始数组的大小和M - 分割数。
下面的工作代码（我用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
@Gumbo的答案是明确的，可操作的，但消耗大量的时间长度时（A），比400大和P不是8个大是因为算法是一种以效益为他说，暴力破解。
事实上，一个非常快的解决方案是使用动态规划 。
给定的正整数的数组A和正整数P，该阵列的单独为P不重叠的子阵列使得每个子阵列的总和和所述子阵列的完美总和（总和（A）/ P）之间的差为最小。
测量：
，其中
这可以确保总和的平衡，因为它使用的定义标准偏差 。
Persuming该数组A具有N个元素; A的最后i个元素时分割为J个的子阵列Q（I，J）表示最小测量值。 d（I，J）的装置(sum(B)-sum(A)/P)^2时阵列B由第i〜的第j个元素（ 0<=i<=j<N
问题的最小度量是计算Q（N，P）。 我们发现：
Q(N,P)=MIN{Q(N-1,P-1)+D(0,0); Q(N-2,P-1)+D(0,1); ...; Q(N-1,P-1)+D(0,N-P)}
因此，它喜欢可以通过动态规划来解决。
Q(i,1) = D(N-i,N-1)
Q(i,j) = MIN{ Q(i-1,j-1)+D(N-i,N-i);
Q(i-2,j-1)+D(N-i,N-i+1);
...;
Q(j-1,j-1)+D(N-i,N-j)}
因此，该算法的步骤是：
1. Cal j=1:
Q(1,1), Q(2,1)... Q(3,1)
2. Cal j=2:
Q(2,2) = MIN{Q(1,1)+D(N-2,N-2)};
Q(3,2) = MIN{Q(2,1)+D(N-3,N-3); Q(1,1)+D(N-3,N-2)}
Q(4,2) = MIN{Q(3,1)+D(N-4,N-4); Q(2,1)+D(N-4,N-3); Q(1,1)+D(N-4,N-2)}
... Cal j=...
P. Cal j=P:
Q(P,P), Q(P+1,P)...Q(N,P)
The final minimum Measure value is stored as Q(N,P)!
To trace each subarray's length, you can store the
MIN choice when calculate Q(i,j)=MIN{Q+D...}
相比纯粹的暴力破解算法消耗
我想知道下面是否工作：
尽快从左边走，因为sum > sigma ，分支为两个，一个包括推动它在不适用的价值，和一个。 递归地处理数据向右rightSum = totalSum-leftSum和rightP = P-1
因此，在一开始，和= 60
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
然后，对于2 4 6 7 ，总和= 19>西格玛，所以分成：
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
然后我们处理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与P = 4-1和sum = 60-12和sum = 60-19分别。
这导致，我认为，O（P * N）。
这可能是一个问题，当1倍或2的值是迄今为止最大的，但是，对于任何值> =西格玛，我们或许可以只是把在它自己的分区（预处理阵列找到这些可能是最好的主意（和减少总和适当））。
如果成功，它应该有希望尽量减少加总方误差（或接近），这似乎是所需的措施。
我提出了一种基于回溯的算法。 随机选择的主要功能从原始数组选择一个元素，并将其添加到分配的阵列。 对于每一个除了将检查以获得比原来更好的解决方案。 这将通过使用计算偏差的功能，区分每一个加入到页的新元素来实现。 无论如何，我认为这将是很好的，你不能达到预期的解决方案将迫使程序结束循环添加一个原始变量。 通过所需的溶液I是指相对于由从如果条件强加的条件添加的所有元素。
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迭代= 0而{...如果（initial_deviation>偏差（difference_vector）+ additional_amount）ExtractFromBackVectorAndPutOnSecondVector（list_vector，矢量）如果（迭代> MAX_ITERATION）{迭代= 0 aditional_amout + = 1 / some_constant}迭代++ //删除第二如果从第一个版本}
你的问题是非常相似的，或相同的最小最速调度问题 ，这取决于你如何定义你的目标。 在你希望尽量减少最大的情况下|sum_i - sigma| ，正是这个问题。
由于维基百科的文章中提到，这个问题是NP完全为p > 2 。 Graham的列表调度算法是最佳的p <= 3 ，并且提供的近似比2 - 1/p 。 您可以检查出其他算法及其近似维基百科的文章。
此页面上提供的所有算法要么解决了不同的目标，不正确/不理想，或可用于NP解决任何问题:)
这是非常相似的一维装箱问题的情况下，看到http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml 。 在相关的书， 算法设计手册 ，Skienna表明第一配合降低的做法 。 即计算出你的块大小（平均=总和/ N），然后分配剩余的最大的对象为有空间为它的第一格。 你要么得到的地方，你不得不重新开始填充一个垃圾桶，或者如果你很幸运，你得到一个完美的契合点。 作为Skiena规定“首次适应减少有一个直观的吸引力了，因为我们第一包笨重的对象，并希望小东西能够填满裂缝。”
由于以前的海报说，这个问题看起来像它的NP完全问题，所以你不会在合理的时间内完美地解决它，你需要寻找启发。
最近，我需要这个，做了如下;
[[sum:0],[sum:0]...[sum:0]] initial阵列。 这是JS代码。
function groupTasks(tasks,groupCount){ var sum = tasks.reduce((p,c) => p+c), initial = [...Array(groupCount)].map(sa => (sa = [], sa.sum = 0, sa)); return tasks.sort((a,b) => ba) .reduce((groups,task) => { var group = groups.reduce((p,c) => p.sum < c.sum ? p : c); group.push(task); group.sum += task; return groups; },initial); } var tasks = [...Array(50)].map(_ => ~~(Math.random()*10)+1), // create an array of 100 random elements among 1 to 10 result = groupTasks(tasks,7); // distribute them into 10 sub arrays with closest sums console.log("input array:", JSON.stringify(tasks)); console.log(result.map(r=> [JSON.stringify(r),"sum: " + r.sum])); 您可以使用最大流量算法。
