【编程题目】一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值★★ （自己没有做出来！！）

45.雅虎（运算、矩阵）：

2.一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值 比如{3，2，4，3，6} 可以分成

{3，2，4，3，6} m=1;

{3,6}{2,4,3} m=2

{3,3}{2,4}{6} m=3 所以 m 的最大值为 3

回头再自己写！！

网上答案，验证正确。http://blog.csdn.net/peng_weida/article/details/7741888

/*

45.雅虎（运算、矩阵）：

2.一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值

比如{3，2，4，3，6}  可以分成{3，2，4，3，6} m=1;

{3,6}{2,4,3} m=2

21

{3,3}{2,4}{6} m=3  所以 m 的最大值为 3

*/

#include <cstdio>

#include <cstdlib>

#define NUM    7

int maxShares(int a[], int n);

//aux[i]的值表示数组a中第i个元素分在哪个组,值为0表示未分配

//当前处理的组的现有和 + goal的值 = groupsum

int testShares(int a[], int n, int m, int sum, int groupsum, int aux[], int goal, int groupId);

int main()

{

    int a[] = {, , , , , , };

        //{2,2,2,3,3,4,8} ;

        //{1,2,2,3,4,6};

        //{2, 6, 4, 1, 3, 9, 7, 5, 8, 10};

    //打印数组值

    printf("数组的值：");

    for (int i = ; i < NUM; i++)

        printf(" %d ", a[i]);

    printf("\n可以分配的最大组数为：%d\n", maxShares(a, NUM));

    system("pause");

    return ;

}

int testShares(int a[], int n, int m, int sum, int groupsum, int aux[], int goal, int groupId)

{

    if (goal < )

        return ;

    if (goal == )

    {

        groupId++;

        goal = groupsum;

        if (groupId == m+)

            return ;

    }

    for (int i = ; i < n; i++)

    {

        if (aux[i] != )

            continue;

        aux[i] = groupId;

        if (testShares(a, n, m, sum, groupsum, aux, goal-a[i], groupId))

            return ;

        aux[i] = ;                //a[i]分配失败，将其置为未分配状态

    }

    return ;

}

int maxShares(int a[], int n)

{

    int sum = ;

    int *aux = (int *)malloc(sizeof(int) * n);

    for (int i = ; i < n; i++)

        sum += a[i];

    for (int m = n; m >= ; m--)

    {

        if (sum%m != )

            continue;

        for (int i = ; i < n; i++)

            aux[i] = ;

        if (testShares(a, n, m, sum, sum/m, aux, sum/m, ))

        {

            //打印分组情况

            printf("\n分组情况：");

            for (int i = ; i < NUM; i++)

                printf(" %d ", aux[i]);

            free(aux);

            aux = NULL;

            return m;

        }

    }

    free(aux);

    aux = NULL;

    return ;

}