美文网首页
面试题:数组分割使子数组的和最接近

面试题:数组分割使子数组的和最接近

作者: 四月_兔 | 来源:发表于2018-12-29 23:33 被阅读0次
    描述:一个一维数组比如 $arr = [1,3,4,5,6,7,10,2,3,4]; 把他拆成两个数组 且这两个数组值的和最接近

    基本思路是:先举个例子哈,比如现在有一大堆零钱,有100一张,50一张,1块的 5毛的 各种面值都有,假如叫你和你对象(当然程序员很难有对象,暂且new一个吧)分,一般小时候分东西就会有这种思路:每次从中拿一张,只能拿一张,谁拿的算谁的。你会怎么拿??你当然会选里面面值最大的呀(这也是你没对象的原因咯),但是你对象也会这么想,这样的结果看起来是公平的(小时候类似这样的真以为是公平的),说到这里是不是有点小思路了??但是,还有个但是哦,如果下面有一张面值很大的 就是剩下的全加起来也没它大,所以按这样轮流选其实是不公平的,所以呢如果你手里的钱的总和比你对象的多,那么不好意思为了公平得让她去拿,也就是谁多谁就得停一手 让另一个人去拿,另一个人又去拿最大的一张

    不废话 直接上代码吧:

    function fen($arr=[]){
        static $one = 0;        //第一个数组值得和
        static $oneArr = [];    //第一个数组
    
        static $two = 0;        //第二个数组值得和
        static $twoArr = [];    //第二个数组
        static $data = [];
    
        $leng = count($arr);
    
        if ($one > $two) {  //如果第一个数组比第二个大,那就让另一个去挑 否则自己再挑
            $two += $arr[$leng-1];
            $twoArr[] = $arr[$leng-1];
        } else {
            $one += $arr[$leng-1];
            $oneArr[] = $arr[$leng-1];
        }
    
        unset($arr[$leng-1]);  //分走了就得去掉
    
        if (count($arr) < 1) {
            $data = [
                'one' => ['one' => $one, 'one_arr' => $oneArr],
                'two' => ['two' => $two, 'two_arr' => $twoArr]
            ];
        } else {
            fen($arr);  //上面的代码就是往其中一个子数组分了一个值 剩下的我们再继续按刚才的逻辑去分,所以来个递归
        }
        return $data;
    }
    
    $arr = [79,1,3,6,0,3,2,5,99,100,1000,500,400];
    sort($arr);    //对数组排序
    $result = fen($arr);
    echo "<pre>";
    print_r($result);
    

    打印结果:

    Array
    (
        [one] => Array
            (
                [one] => 1099
                [one_arr] => Array
                    (
                        [0] => 1000
                        [1] => 99
                        [2] => 0
                    )
            )
        [two] => Array
            (
                [two] => 1099
                [two_arr] => Array
                    (
                        [0] => 500
                        [1] => 400
                        [2] => 100
                        [3] => 79
                        [4] => 6
                        [5] => 5
                        [6] => 3
                        [7] => 3
                        [8] => 2
                        [9] => 1
                    )
    
            )
    
    )
    

    相关文章

      网友评论

          本文标题:面试题:数组分割使子数组的和最接近

          本文链接:https://www.haomeiwen.com/subject/uxemlqtx.html