题目：.一个整数数组a，长度为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求出数组和SUM。
2假设可以分成m组，找到一个合适的m.
m的取值为sum%m=0,m<=sum/max(a[i])
3 从大到小验证找到一个可行的m值.
此过程可以用递归。f(a,m)=f(a-set,m-1)
思路一：
将整个数组作为一个集合，最大的可能值就是集合的大小了，最小肯定是1，那么从2开始一次判断。如果集合可被k等分，那么首先集合的和能够被k整除，如果这个条件满足，则重复k-1次从这个集合中取出和为sum/k的子集合。
取子集合的算法是一个递归的思想，详见153楼
其他几个题目都是比较经典的问题，不赘述。
思路二：
ANSWERTwo restrictions on m, 1) 1 <= m <= n; 2) Sum(array) mod m = 0NOTE: no hint that a[i]>0, so m could be larger than sum/max;So firstly prepare the candidates, then do a brute force search on possible m’s.In the search , a DP is available, since if f(array, m) = OR_i( f(array-subset(i), m) ), where Sum(subset(i)) = m.
int maxShares(int a[], int n) { int sum = 0; int i, m; for (i=0; i<n; i++) sum += a[i]; for (m=n; m>=2; m–) { if (sum mod m != 0) continue; int aux[n]; for (i=0; i<n; i++) aux[i] = 0; if (testShares(a, n, m, sum, sum/m, aux, sum/m, 1)) return m; } return 1;}
int testShares(int a[], int n, int m, int sum, int groupsum, int[] aux, int goal, int groupId) { if (goal == 0) { groupId++; if (groupId == m+1) return 1; } for (int i=0; i<n; i++) { if (aux[i] != 0) continue; aux[i] = groupId; if (testShares(a, n, m, sum, groupsum, aux, goal-a[i], groupId)) { return 1; } aux[i] = 0; }}
Please do edge cutting yourself, I’m quite enough of this…
版权声明：本文为博主原创文章，未经博主允许不得转载。
不求与人相比，但求超越自己，要哭就哭出激动的泪水，要笑就笑出成长的性格。
