讨论数量:
- 计算出原始数组的平均值
- 定义两个数组 arr_1 和 arr_2
- 遍历原始数组,向 arr_1 中添加元素,每次添加元素计算 arr_1 的总和。如果 arr_1 的总和大于平均值,则将此元素放入 arr_2 中。
我真是太天真了,上面的算法确实有问题。找到一个蠢办法:将原始数组进行组合,穷举出所有可能的组合。然后遍历这些组合,找出组合求和值与平均值最接近的组合:
// 递归方法
function getAnswer($amount, $need){
if($need == 1){
for ($i=1;$i<=$amount;$i++){
$rst[] = [$i];
}
return $rst;
} else {
$rst = getAnswer($amount-1, $need-1);
foreach($rst as $v){
for ($i=$v[$need-2]+1;$i<=$amount;$i++){
$v[$need-1] = $i;
$result[] = $v;
}
}
return $result;
}
}
// 穷举出所有的组合
function getAllCombination($arr){
$length = count($arr);
for ($i=1; $i <= $length; $i++) {
$sub = getAnswer($length, $i);
foreach ($sub as $k => $v){
$cell = [];
foreach ($v as $per_sub){
$cell[] = $arr[$per_sub - 1];
}
$rst[] = $cell;
}
}
return $rst;
}
// 进行测试
$arr = [2,2,3,3,4,6,10];
$avg = array_sum($arr)/2;
// 获取所有可能的组合
$allCombination = getAllCombination($arr);
// 每个组合与平均值的差
$difference = $avg;
// 最终筛选出的结果
$result = [];
foreach ($allCombination as $key => $value) {
$diff = abs(array_sum($value) - $avg);
if($diff < $difference){
$difference = $diff;
$result = $value;
}
}
dd($result);
结果:
array:3 [▼
0 => 2
1 => 3
2 => 10
]
个人想法哈, 没具体验证, 将数组从大到小排序后的$arr
, 创建 $arr1
,$sum1
和$arr2
,$sum2
, 遍历$arr as $item
如果$sum1>=$sum2 则将$item给$arr2 就是将$item给总和小的那个子数组
$gavr = function (array $arr) {
$arr1 = [];
$arr2 = [];
$sum1 = 0;
$sum2 = 0;
rsort($arr);
foreach ($arr as $item) {
if ($sum1 >= $sum2) {
$arr2[] = $item;
$sum2 += $item;
} else {
$arr1[] = $item;
$sum1 += $item;
}
}
return [$arr1, $arr2];
};
$arr = [2, 2, 3, 3, 4, 6, 10];
[$arr1, $arr2] = $gavr($arr);
看了楼上两位老哥提到了一个名词【动态规划】,本人不甚了解,于是乎去查询研究了一下,故而恍然大悟,学到了新的知识。
在此把楼主的问题作为考试题目,自己解答了下加深一下印象:
$arr = [2,2,3,3,4,6,10];
$len = sizeof($arr);
//$sum = array_sum($arr); //总和30
$avg = array_sum($arr)/2;
//30/2 =15平均值;
//将数组拆分成两个数组,两个数组值相差最小
//列如
//$a = [2,3,4,6]; //15
//$b = [2,3,10]; //15
$d1 = [];
$d2 = [];
for($i = 0; $i <= $len; $i++){
for($j = 0; $j <= $avg; $j++){
$d1[$i][$j] = 0;
$d2[$i][$j] = [];
}
}
for($i = 1; $i <= $len; $i++){
for($j = 1; $j <= $avg; $j++){
$d1[$i][$j] = $d1[$i-1][$j];
$d2[$i][$j] = $d2[$i-1][$j];
if(!isset($d1[$i-1][$j-$arr[$i-1]])) continue;
$tmp = $d1[$i-1][$j-$arr[$i-1]] + $arr[$i-1];
if ($tmp > $d1[$i][$j]) {
$d1[$i][$j] = $tmp;
$d2[$i][$j] = $d2[$i-1][$j-$arr[$i-1]];
$d2[$i][$j][$i-1] = $arr[$i-1];
}
}
}
for ($i = 1; $i <= $len; $i++){
if ($arr[$i-1] < 10) {
echo " " . $arr[$i-1] . ": ";
} else {
echo $arr[$i-1] . ": ";
}
for ($j = 1; $j <= $avg; $j++){
if ($d1[$i][$j] < 10) {
echo " " . $d1[$i][$j] . " ";
} else {
echo $d1[$i][$j] . " ";
}
}
echo PHP_EOL;
}
$r = end($d2);
$arr1 = end($r);
$arr2 = array_diff_assoc($arr, $arr1);
print_r($arr1);
print_r($arr2);
最终结果符合预期,感谢!
推荐文章: