[求解]数组,分成俩个数组,数组值之和的相差最小。

$arr = [2,2,3,3,4,6,10]
$sum = array_sum($arr); //总和30
//30/2 =15平均值;
//将数组拆分成两个数组,两个数组值相差最小
//例如
$a = [2,3,4,6]  //15
$b = [2,3,10]   //15

要怎么写呢?

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 6
  1. 计算出原始数组的平均值
  2. 定义两个数组 arr_1 和 arr_2
  3. 遍历原始数组,向 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
]
2年前 评论
zccxvas110 (楼主) 2年前
LiamHao (作者) 2年前
zccxvas110 (楼主) 2年前
LiamHao (作者) 2年前
zccxvas110 (楼主) 2年前
LiamHao (作者) 2年前

@LiamHao 错了你仔细想想,这是道动态规划题

2年前 评论
LiamHao 2年前
lidongyoo (作者) 2年前
zccxvas110 (楼主) 2年前
zccxvas110 (楼主) 2年前
lidongyoo (作者) 2年前
LiamHao 2年前
zccxvas110 (楼主) 2年前
lidongyoo (作者) 2年前
lidongyoo (作者) 2年前
zccxvas110 (楼主) 2年前
porygonCN

个人想法哈, 没具体验证, 将数组从大到小排序后的$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);
2年前 评论
porygonCN (作者) 2年前
porygonCN (作者) 2年前
lidongyoo 2年前
zccxvas110 (楼主) 2年前

首评已更新,办法比较老套,效率是个问题,但是能用。

2年前 评论

看了楼上两位老哥提到了一个名词【动态规划】,本人不甚了解,于是乎去查询研究了一下,故而恍然大悟,学到了新的知识。
在此把楼主的问题作为考试题目,自己解答了下加深一下印象:


$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);

最终结果符合预期,感谢! :yum:

2年前 评论
zccxvas110 (楼主) 2年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!