将一组数随意分成三份,求每一份的和,要求最大和与最小和相差最小的算法,

Question

将一组数随意分成三份,求每一份的和,要求最大和与最小和相差最小的算法,

Answer 1

假设输入的所有数据是正整数（有负数的情况会比较复杂,之后讨论）,存储在数组unsigned int input[m]里,数组长度是m,从0到m-1是所有数.
你需要一个排序算法将input[]从小到大排列,最小的input[0].
使用三个变量保存三组数的和,称为sum[0],sum[1],sum[2],把输入数字从大到小依次放入当前三个和中最小的那一个,直到所有数字放完,最大的和最小的之间的差就是结果.
使用C语言的话如下：
int mindiff(unsigned int input[], int length) //此时input是排序完毕的,length是数组长度
{
if(length=0;i--)//从第四大的数开始
{
sum[minSumIndex]+=input[i];
minSumIndex=getMinSumIndex(sum);
}
if(sum[(minSumIndex+1)%3]>sum[(minSumIndex+2)%3])
return sum[(minSumIndex+1)%3] - sum[minSumIndex];
else
return sum[(minSumIndex+2)%3] - sum[minSumIndex];
}
int getMinSumIndex(int sum[])
{
int index=0
if(sum[1]