我有一个长度为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）之间的差异最小。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
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
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)
@Gumbo的回答非常清晰易懂，但是当A数组长度大于400且P大于8时，它会消耗大量时间。这是因为该算法有点类似于暴力搜索，虽然有一定的优势。
实际上，一种非常快速的解决方案是使用动态规划。
给定一个由正整数组成的数组A和一个正整数P，将数组A分成P个不重叠的子数组，使得每个子数组的和与子数组的完美和（即A数组元素和除以P）之间的差异最小。
度量：
，其中
是子数组
的元素总和，
是P个子数组的平均值。
这可以确保和的平衡，因为它使用了标准差的定义。
假设数组A有N个元素；Q(i,j)表示将A数组的最后i个元素分成j个子数组时的最小度量值。D(i,j)表示当数组B由A数组的第i~j个元素组成时的(sum(B)-sum(A)/P)^2（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...}
空间用于 D(i,j);
时间用于计算 Q(N,P)
与纯暴力算法相比，其消耗的时间为
。
$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
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
} 你可以通过添加一些代码来增加计算偏差的数量，从而改变这个问题。 额外的数量=0 迭代=0 while { ... 如果(initial_deviation>Deviation(difference_vector)+additional_amount) ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector) 如果(iteration>max_iteration) { iteration=0 aditional_amout+=1/some_constant } 迭代++ //从第一个版本中删除第二个if }
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
对于2 4 6 7，总和为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_i - sigma|的最大值，那么它就是那个问题。
正如维基百科文章所引用的，对于p > 2，此问题是NP完备的。 Graham的列表调度算法在p <= 3时是最优的，并且提供了一个近似比2-1/p。你可以查看维基百科文章了解其他算法及其近似度。
此页面上给出的所有算法都是要么解决不同的目标问题，要么错误/次优，要么可以用来解决任何NP问题 :)
这与一维装箱问题非常相似，参见http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml。在相关书籍The Algorithm Design Manual中，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) => 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]));你可以使用最大流算法。
(14,14,14,14,19)的不良度为20，而(15,14,16,14,16)的不良度为4。当然，你可以尝试调整指数。 - user824425