求平均分配算法

来源：百度知道 编辑：UC知道 时间：2024/06/08 01:23:39
假设有按升序排列好的100个数，如何实现将其分为5份（每份中数字的个数不用相等），并使得每份中所有数之和大致相等？例如：这100个数之和为1000，则要使每份数字的和与（1000/5）相差不超过5%。
另外，每份中最好是大数和小数都要有，即大小搭配～

/* 是不是这样？最大的5个数分别放在5份之中，然后从后向前扫描，看这5份谁的总和最少，最少的就把当前数分给它，直到结束，本人认为这是最平均的 */

#include <stdio.h>
#include <string.h>

int array_sum(int *array, int length)
{
int i, sum = 0;
for (i=0; i<length; i++)
{
sum += array[i];
}
return sum;
}

void input_array(int *array, int *i, int value)
{
array[(*i)] = value;
(*i)++;
}

int main(void)
{
int i, j, k, t, a[100];
int group[5][100];
int g[5];
for (i=0; i<100; i++) /* 可以自己输入数据 */
{
a[i] = i;
}
memset(group, 0, sizeof(group));
memset(g, 0, sizeof(g));

for (i=99; i>=0; i--)
{
k = 0; /* 先假定为第0号组 */
t = array_sum(group[0], 100);
for (j=1; j<5; j++)
{
if (t > array_sum(group[j], 100))
{
t = array_sum(group[j], 100); /* 找出最小的 */
k = j; /* 记住是哪一组 */
}
}