问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:
P=(S1-S2)^2+(S1-S3)^2+……+(S1-Sk)^2+(s2-s3)^2+……+(Sk-1-Sk)^2
问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉
程序说明:
数组:a[1],a[2],...A[N]存放原数
s[1],s[2],...,s[K]存放每个部分的和
b[1],b[2],...,b[N]穷举用临时空间
d[1],d[2],...,d[N]存放最佳方案
程序:

program exp4;
Var i,j,n,k : integer;
a :array [1..100] of integer;
b,d:array [0..100] of integer;
s :array[1..30] of integer;
begin 
readln(n,k);
for I:=1 to n do read(a[I]);
for I:=0 to n do b[I]:=1;
cmin:=1000000;
while (b[0]=1) do
begin
    for I:=1 to k do  s[i]:=0;    
for I:=1 to n do 
     s[b[i]]:=s[b[i]+a[i]];    
sum:=0;
for I:=1 to k-1 do
for j:=  i+1 to k do  
sum:=sum+(s[I]-s[j])*(s[I]-s[j]);
if    (cmin>sum)     then 
begin
cmin:=sum;
for I:=1 to n do d[I]:=b[I];
end;
j:=n;
while     (b[j]>k)      do j:=j-1;
b[j]:=b[j]+1;
for I:=j+1 to n do     b[i]:=1;     
end;
writeln(cmin);
for I:=1 to n do write(d[I]:4);
writeln;
end.