学步园

/*
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

将整个数组作为一个集合，最大的可能值就是集合的大小了，最小肯定是1，
那么从2开始一次判断。如果集合可被k等分，
那么首先集合的和能够被k整除，条件满足，则重复k-1次从这个集合中取出和为sum/k的子集合。

*/ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool testShare(int s[],int n,int m,int groupSum,int goal,int aux[],int groupId)
{
	if(goal==0)// groupSum为每组的和，goal表示还剩多少，groupId现在是第几组
	{
		groupId++;//一组分配完，ID++，goal重置 
		goal=groupSum;
		if (groupId==m+1)// 已经分完m组	
			return true;
	}
	
	for(int i=0;i<n;++i)
	{
		if(aux[i]) 
			continue; //已经选过的
		aux[i]=groupId;//标记这是放在第几组 
		if(testShare(s,n,m,groupSum,goal-s[i],aux,groupId)) 
								//判断goal-s[i]，可行否 
			return true;
			
		aux[i]=0; //还原，继续下次 
	}
	return false;
}


int maxShare(int s[],int len)
{
	
	int i,m,sum=0;
	int aux[len];
	
	
	for(i=0;i<len;i++) 
		sum+=s[i]; //求总和
		
	for(m=len;m>=2;--m)//m表示分成几组，递减 
	{
		if(sum%m!=0) //不能被m整除，肯定不能平分
			continue; 
		memset(aux,0,sizeof(aux));//aux表示分成不同的组
		 
		//testShare(s[],n, m, groupSum, goal, aux[], groupId) 
		if(testShare(s,len,m, sum/m,sum/m,aux,1))
		{
			printf("具体分配如下：\n");
			for(i=1;i<=m;i++)
			{
				for(int j=0;j<len;j++)
					if(aux[j]==i)
						printf("%d ",s[j]);
				if(i!=m)
					printf(" , ");
			}
			printf("\n");
			return m;
		}
	}
	return 1;
}

int main()
{
	int a[] ={5,4,2,2,1,4,6};
	int b[] ={3,2,4,3,6,1,5,4,2,5,6,1};
	int c[] ={3,2,4,3,6};
	
	printf("数组的值：");  
    for(int i=0;i<sizeof(a)/sizeof(int);i++)  
        printf("%d ",a[i]); 
	printf("\n"); 
    printf("可以分配的最大组数为：%d\n",maxShare(a,sizeof(a)/sizeof(int))); 
    
    
    printf("**************************************\n");
    printf("数组的值：");  
    for(int i=0;i<sizeof(b)/sizeof(int);i++)  
        printf("%d ",b[i]); 
	printf("\n"); 
    printf("可以分配的最大组数为：%d\n",maxShare(b,sizeof(b)/sizeof(int))); 
    
    
     printf("**************************************\n");
    printf("数组的值：");  
    for(int i=0;i<sizeof(c)/sizeof(int);i++)  
        printf("%d ",c[i]); 
	printf("\n"); 
    printf("可以分配的最大组数为：%d\n",maxShare(c,sizeof(c)/sizeof(int))); 
}