整数数组，长度为n，分为m份。求m最大值 - crazyhacking的专栏 - 博客频道 - CSDN.NET

题目1251：序列分割
http://ac.jobdu.com/problem.php?pid=1251
整数数组，长度为n，分为m份。求m最大值 - crazyhacking的专栏 - 博客频道 - CSDN.NET
题目：.一个整数数组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

X. 
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的子集合。
45-数组分为m份和相等

12	int verify_group(int* a, int size, int sum, int d, int* aux,

13	int target, int group_id) {

14	if (target < 0) {

15

return 0;

16	} else if (target == 0) {

17	group_id++;

18	target = sum / d;

19

20	if (group_id == d+1)

21

return 1;

22

}

23

24	for (int i = 0; i < size; i++) {

25	if (aux[i] != 0)

26

continue;

27

28	aux[i] = group_id;

29	if (verify_group(a, size, sum, d, aux, target - a[i], group_id))

30

return 1;

31

32	aux[i] = 0;  // a[i]分配失败，重新置为未分配状态

33

}

34

return 0;

35

}

36

37	int max_group(int* a, int size) {

38

// 求数组的和

39	int sum = 0;

40	for (int i = 0; i < size; i++)

41	sum += a[i];

42

43	int* aux = new int[size];

44	for (int d = size; d >= 2; d--) {

45	if (sum % d != 0)  // 不可能划分成d份

46

continue;

47

48	memset(aux, 0, sizeof(int) * size);

49

50	if (verify_group(a, size, sum, d, aux, sum / d, 1)) {

51

//分组成功，打印

52	cout << "group_index:" << endl;

53	print(aux, size);

54

55	delete []aux;

56

return d;

57

}

58

}

59

60	delete aux;

61

return 1;

62

}

http://blog.csdn.net/zhang_hui_cs/article/details/25545677

1. // 从数组中找出和为sum的组合。  
2. bool DivideArray(int arr[], bool tags[], int size, int sum)  
3. {  
4.     if (sum < 0)  
5.         return false;  
6.     else if (sum == 0)  
7.         return true;  
8.   
9.     for (int i = size - 1; i >= 0; i--)  
10.     {  
11.         if ((!tags[i]) && (arr[i] <= sum))  
12.         {  
13.             tags[i] = true;  
14.             if (DivideArray(arr, tags, size, sum - arr[i]))  
15.                 return true;  
16.             else  
17.                 tags[i] = false;  
18.         }  
19.     }  
20.   
21.     return false;  
22. }  
23.   
24. int DivideArray(int arr[], int size)  
25. {  
26.     if (size <= 1)  
27.         return (size >= 0 ? size : 0);  
28.   
29.     // 计算数组元素之和  
30.     int m, sum, i;  
31.     m = sum = 0;      
32.     for (int i = 0; i < size; i++)  
33.         sum += arr[i];  
34.   
35.     bool *tags = new bool[size];  
36.   
37.     for (m = size; m > 1; m--)  
38.     {  
39.         if (sum % m != 0)  
40.             continue;  
41.   
42.         memset(tags, 0, sizeof(bool) * size);  
43.   
44.         for (i = 0; i < size; i++)  
45.         {  
46.             if (!tags[i])  
47.             {  
48.                 // 如果元素i没有分块，就将其分块。  
49.                 tags[i] = true;  
50.   
51.                 // 如果i元素分块失败，就跳出for循环，m值失败。  
52.                 if (!DivideArray(arr, tags, size, sum / m - arr[i]))  
53.                     break;  
54.             }  
55.         }  
56.   
57.         if (i >= size)  
58.         {  
59.             // 如果i>=size，表示数组元素都被成功分配，此时m为最大值。  
60.             break;  
61.         }  
62.     }  
63.           
64.     return m;  
65. } 

X. http://t.jobdu.com/thread-7974-1-1.html
剪枝1：由大到小顺序排列，每次选择重上次选择的后一个开始。
剪枝2：如果一个数字把一组填满了，不需要考虑用更小的木棍填补这一组了，进行对下一组的搜索。
剪枝3：设对一组的搜索开始时，当前尚未用的最大的数字是a，如果把a选入不行，那么目前的状态应舍弃，因为这个数字a是必然要处理的，而放到后面处理，只会可用数字更少，而亦必然不可以。
剪枝4：由于数字已排序，前面一个数字尝试后不行，则跳过下面同样的数字。
http://blog.csdn.net/xiexingshishu/article/details/27242891
The solve method is nit implemented well.

1.     public boolean Try(int m)   
2.     {  
3.         if (sum % m != 0) return false;  
4.           
5.         Arrays.fill(vis, false);  
6.           
7.         return dfs(sum / m, m, m, 0);  
8.     }  
9.       
10.     public boolean dfs(int cnt, int max, int re, int s)  
11.     {  
12.         if (cnt == 0) return true;  
13.           
14.         if (re == 0) {  
15.             //找到一个组合的值为max  
16.             return dfs(cnt - 1, max, max, 0);  
17.         }  
18.           
19.         for (int i = s; i < n; i++) {  
20.             if (vis[i] || re - numArr[i] < 0) continue;  
21.               
22.             vis[i] = true;  
23.             if (dfs(cnt, max, re - numArr[i], i + 1)) return true;  
24.               
25.             vis[i] = false;  
26.             //剪枝在找到一个组合的值为max后，接下来的不能成立  
27.             if (re - numArr[i] == 0) break;  
28.             //剪枝在无法找到构成max  
29.             if (max == re) break;  
30.               
31.             //剪枝在未选择时，跳过相同的  
32.             while (i + 1 < n && numArr[i + 1] == numArr[i]) i++;  
33.         }  
34.           
35.         return false;  
36.     }  

TODO: http://my.oschina.net/dapengking/blog/92183
Read full article from 整数数组，长度为n，分为m份。求m最大值 - crazyhacking的专栏 - 博客频道 - CSDN.NET