我有一个长度为 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)。
先感谢您。
首先，让我们通过为每个可能的解决方案指定输入、输出和度量来形式化您的优化问题（我希望这符合您的兴趣）：
给定一个正整数数组A和一个正整数P，将数组A分成P个不重叠的子数组，使得每个子数组的和与子数组的完美和 (sum( A )/ P ) 之间的差异最小.
输入：正整数数组A；P是一个正整数。
输出：由P个非负整数组成的数组SA表示A的每个子数组的长度，其中这些子数组长度的总和等于A的长度。度量： abs(sum( sa )-sum( A )/ P ) 对于每个sa ∈ { sa |是最小的 sa = ( A i , ..., A i +<em>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个非负整数的组合，总和为 length( A )，以表示所有可能的有效解决方案。尽管这确保不会错过有效的解决方案，但它基本上是一种蛮力方法，其好处是我们可以省略一些不能比我们最好的解决方案更好的分支。例如，在上面的例子中，如果我们已经有了一个measure ≤ 38的解，我们就不需要用 [9,…] ( measure > 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替换为表示有效解决方案的余数（这里很少优化），或者如果存在则返回列表中没有值。只需将最右边的整数加一，如果增量超出总限制，则返回。None0NoneNonenextNone
现在您只需要创建一个问题实例，初始化全局变量并bt使用 root 调用：
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)
如果我在这里没记错的话，另一种方法是动态编程。
如果创建了n个子数组，您可以将P [ pos , n ] 定义为累积到位置pos的最小可能“惩罚” 。显然有一些位置 pos' 这样
P[pos', n-1] + 罚分(pos', pos) = P[pos, n]
您可以最小化 pos' = 1..pos。
天真的实现将在 O(N^2 * M) 中运行，其中 N - 原始数组的大小和 M - 分割数。
@Gumbo 的答案是明确且可操作的，但是当 length(A) 大于 400 且 P 大于 8 时会花费大量时间。这是因为该算法有点像他所说的那样具有好处的蛮力。
事实上，一个非常快速的解决方案是使用动态规划。
给定一个正整数数组 A 和一个正整数 P，将数组 A 分成 P 个不重叠的子数组，使得每个子数组的和与子数组的完美和之间的差 (sum(A)/P) 最小.
度量：
，其中
是子数组 元素的总和
，
是 P 个子数组总和的平均值。
这样可以保证 sum 的平衡，因为它使用了Standard Deviation的定义。
假设数组 A 有 N 个元素；Q(i,j)表示将 A 的最后 i 个元素拆分为 j 个子数组时的最小 Measure 值。D(i,j)表示(sum(B)-sum(A)/P)^2数组 B 由 A ( 0<=i<=j<N) 的第 i~j 个元素组成。
问题的最小度量是计算 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...}
D(i,j) 的空间；
计算 Q(N,P) 的时间
与纯暴力破解算法相比，消耗
时间。
下面的工作代码（我使用 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
这与一维装箱问题的情况非常相似，参见http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml。在相关的《算法设计手册》一书中，Skienna 提出了一种首次拟合递减方法。即找出你的 bin 大小（平均值 = sum / N），然后将最大的剩余对象分配到第一个有空间的 bin 中。你要么到了不得不开始过度填充垃圾箱的地步，要么如果你很幸运，你会得到一个完美的配合。正如 Skiena 所说，“首次拟合递减对它具有直观的吸引力，因为我们首先打包大件物品，并希望小件物品可以填补裂缝。”
正如之前的海报所说，这个问题看起来是 NP 完全的，所以你不会在合理的时间内完美地解决它，你需要寻找启发式方法。
我提出了一种基于回溯的算法。选择的主函数从原始数组中随机选择一个元素并将其添加到分区数组中。对于每次添加都会检查以获得比原来更好的解决方案。这将通过使用计算偏差的函数来实现，区分每个向页面添加新元素。无论如何，我认为在循环中添加一个原始变量会很好，如果您无法达到所需的解决方案将强制程序结束。通过所需的解决方案，我的意思是添加与 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, vector) if(iteration>max_iteration) { iteration=0 aditional_amout+=1/some_constant } iteration++ //删除第二个 if从第一个版本}
我想知道以下是否可行：
从左边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, 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
然后我们分别处理7 6 3 3 3 4 3 4 4 4 3 3 1and6 3 3 3 4 3 4 4 4 3 3 1和P = 4-1and 。sum = 60-12sum = 60-19
我认为这会导致 O(P*n)。
当 1 或 2 个值迄今为止最大时，这可能是一个问题，但是，对于任何 >= sigma 的值，我们可能可以将其放在它自己的分区中（预处理数组以找到这些可能是最好的主意（并减少适当地求和））。
如果它有效，它应该有望最小化误差平方和（或接近该误差），这似乎是所需的度量。
您的问题与最小制造时间调度问题非常相似或相同，具体取决于您如何定义目标。如果您想最小化最大值|sum_i - sigma|，那就是这个问题。
正如 Wikipedia 文章中提到的，这个问题对于p > 2. Graham 的列表调度算法对 是最优的p <= 3，并提供了一个近似比2 - 1/p。您可以查看 Wikipedia 文章以了解其他算法及其近似值。
此页面上给出的所有算法要么解决不同的目标，不正确/次优，要么可用于解决 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) => b-a)
.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]));您可以使用最大流量算法。