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

$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

原提问地址链接
(因第一次提问发布的类型选择错误,无法选择最佳答案,很抱歉)

《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
最佳答案
// 递归方法
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年前 评论
讨论数量: 3
// 递归方法
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年前 评论

改了下,之前那个自己写的方法有漏洞,没有穷举出全部。这个是抄的

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

算法背包问题

2年前 评论

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