现在的位置: 首页 > 综合 > 正文

PHP 平分数组

2013年03月07日 ⁄ 综合 ⁄ 共 1189字 ⁄ 字号 评论关闭
 1 <?php
 2     /**
 3     *一个整数数组,长度为n,将其分为m 份,使各份的和相等,求m 的最大值
 4     *比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;
 5     *{3,6}{2,4,3} m=2
 6     *{3,3}{2,4}{6} m=3 所以m 的最大值为3
 7     **/
 8 
 9     #解题思路
10     #首先m必须满足两个条件
11     #1. 1<=m<=n
12     #2. sum(a) % m = 0,即sum(a)必须是m的倍数,其中a为待切分数组
13     #解题步骤:
14     #1. m从n开始,依次减小
15     #2. 判断m是否能满足题目条件,如满足,则返回m以及分组信息
16     #对于判断m是否能满足条件,使用辅助数组group_info[]
17     #其中group_info[i]=k表示a[i]被分配到第k组
18 
19     function maxm($a) {
20         $len = count($a);
21         $asum = 0;
22         for ($i = 0; $i < $len; $i++) $asum += $a[$i];
23 
24         #
25         for ($m = $len; $m >= 2; $m--) {
26             if ($asum % $m != 0) continue;
27             $group_info = array(); #分组信息
28             for ($i = 0; $i < $len; $i++) $group_info[$i] = 0;
29             if (test($a, $m, $asum, $group_info, $asum / $m, 1)) 
30                 return array("m" => $m, "group_info" => $group_info);
31         }
32 
33         return array("m"=> 1);
34     }
35 
36     function test($a, $m, $asum, &$group_info, $goal, $group_id) {
37         $len = count($a);
38         $msum = $asum / $m;
39 
40         if ($goal == 0) {
41             $group_id++;
42             $goal = $msum;
43             #所有分组分配结束
44             if ($group_id == $m + 1) return true;
45         } else if ($goal < 0) {
46             return false;
47         }
48         #将数组分组,并判断是否能满足条件
49         for ($i = 0; $i < $len; $i++) {
50             #跳过已分配元素
51             if ($group_info[$i] != 0) continue;
52             $group_info[$i] = $group_id;
53             #分配完a[i]继续往下分配
54             if (test($a, $m, $asum, $group_info, $goal - $a[$i], $group_id)) return true;
55             #a[i]分配失败,重新置为0
56             $group_info[$i] = 0;
57         }
58 
59         return false;
60     }
61 
62     $a = array(3, 2, 4, 3, 6, 2, 2, 2);
63     print_r(maxm($a));
64 ?>

抱歉!评论已关闭.