【算法】分箱子问题 – 第1章-一一网

最近在公司开发业务的时候，遇到了一个实际问题，需要用到算法去求解，而且是涉及最优解的问题，所以写一个系列文章去记录下。听上去是不是有点泪流满脸的感觉，业务开发终于不再是crud，而是要写算法了（手动狗头）。

问题：一批货，有多个箱子，每个箱子里面有不同的型号，现在要求把这批货分开成N个单，每单可以包含多个箱子，但是每个箱子只能属于1单，而且每单里面的型号总数不能大于50个。

求这批货里面的多个箱子，应该怎么切法，能使产生的单数最少？有没有方法能每次都做到最优解？单数最少最优解的意思是：尽量产生最多的能凑满50个型号为1单的情况，剩下不满50个的单独为1单。

举个例子：

     [1] => 17
     [2] => 1
     [3] => 40
     [4] => 27
     [5] => 1
     [6] => 6
     [7] => 1
     [8] => 1
     [9] => 48
     [10] => 43
     [11] => 18
     [12] => 1
     [13] => 1
     [14] => 4
     [15] => 10
     [16] => 13
     [17] => 9
     [18] => 1
     [19] => 1
复制代码

这是一个数组代表一批货，前面的是箱子号，后面的是箱子内型号数，例如第1箱17个，第2箱1个。。。。然后按照上面的规则切分，最优应该是5单，切法如下:

// =======  50
 [9] => 48
 [7] => 1
 [13] => 1
// =======  49
 [10] => 43 
 [8] => 1
 [19] => 1
 [18] => 1
 [12] => 1
 [2] => 1
 [5] => 1
// =======  50
 [3] => 40
 [6] => 6
 [14] => 4
// =======  46
 [4] => 27
 [15] => 10
 [17] => 9
// =======  48
 [11] => 18
 [1] => 17
 [16] => 13
复制代码

但是如果切不好，可能就会变成6单，这样就不是最优解了。

首尾指针法

把箱子号按照箱内型号数顺序排列，取第1个箱，然后取倒数最后1个补，判断够不够50，够就跳出，不够取倒数第2个继续补，直到够50为止，就组合一单。然后unset掉首尾取出的，从剩下的里面继续重复上面的操作。直到剩余数组为空，或者剩余数无法组装够50为止退出。

代码：

<?php
class CAutoDistributeBox
{

    /**
     * 切割箱子组单，每单合并型号为不大于50项，非最优解
     */
    public static function useHeadTailSplit($headBPN){
        arsort($headBPN);  //  按内部型号数顺序排序
        $headBPN2 = $headBPN;
        $bx = [];
        $index = 0;

        while(count($headBPN) > 0) {
            $h = reset($headBPN); // 取头指针放入当前单
            $bx[$index][] = $h;
            array_shift($headBPN);
            $t = 0;
            while ($h + $t < 50) {  // 判断当前单够不够50
                if ($t > 0) {
                    $bx[$index][] = $t;   // 取尾指针放入当前单
                    array_pop($headBPN);
                }
                $h = $h + $t;
                $t = end($headBPN);
                if(count($headBPN) == 0){  // 剩余箱子消费完，退出整个循环
                    break;
                }
            }
            if ($h + $t == 50) {   //  刚好够50，组单
                if ($t > 0) {
                    $bx[$index][] = $t;
                    array_pop($headBPN);
                }
            }
            $index = $index + 1;  // 单的索引+1
        }

        // 把型号数转为对应箱子号，组装回数组里面
        foreach ($bx as $k1 => $v1){
            foreach ($v1 as $k2 => $v2){
                foreach ($headBPN2 as $ke => $sel){
                    if($v2 === $sel){
                        $bx[$k1][$k2] = $ke;
                        unset($headBPN2[$ke]);
                        break 1;
                    }
                }
            }
        }
        return $bx;
    }

}

$arr = [
    1 => 17,
    2 => 1,
    3 => 40,
    4 => 27,
    5 => 1,
    6 => 6,
    7 => 1,
    8 => 1,
    9 => 48,
    10 => 43,
    11 => 18,
    12 => 1,
    13 => 1,
    14 => 4,
    15 => 10,
    16 => 13,
    17 => 9,
    18 => 1,
    19 => 1
];
$arr = CAutoDistributeBox::useHeadTailSplit($arr);
print_r($arr); die;

复制代码

把代码执行下，结果就是上面贴的那样。但是这种方法是不一定能得到最优解的，为什么呢？给一个反例看就知道了。

$arr = [
    1  => 46,
    2  => 4,
    3  => 38,
    4  => 12,
    5  => 28,
    6  => 9,
    7  => 2,
    8  => 11,
    9  => 25,
    10 => 9,
    11 => 6,
    12 => 5,
    13 => 5,
];
复制代码

最优解是4单，但是用首尾指针法跑结果是5单的。排序后：

 [1] => 46 
 [3] => 38 
 [5] => 28 
 [9] => 25 
 [4] => 12 
 [8] => 11 
 [6] => 9 
 [10] => 9 
 [11] => 6 
 [12] => 5 
 [13] => 5 
 [2] => 4 
 [7] => 2 
复制代码

首尾指针法运行结果（5单）：

-- 48
    [1] => 46
    [7] => 2
-- 47
    [3] => 38
    [2] => 4
    [13] => 5
-- 48
    [5] => 28
    [12] => 5
    [11] => 6
    [10] => 9
-- 45 
    [9] => 25
    [6] => 9
    [8] => 11
-- 12
    [4] => 12
复制代码

实际最优解（4单）：

// -- 50
    [1]  => 46
    [2]  => 4
// -- 50
    [3]  => 38
    [4]  => 12
// -- 50
    [5]  => 28
    [6]  => 9
    [7]  => 2
    [8]  => 11
// -- 50
    [9]  => 25
    [10] => 9
    [11] => 6
    [12] => 5
    [13] => 5
复制代码

对比一下两种解法，首尾法太早把小箱给用完了，所以不一定得出最优解。
至于怎么得到最优解呢？高手一下就看出来了，要用到动态规划或者贪心算法，对于这个实际问题，我还在研究中，如果得出解法了我会发一篇新文章的。如果朋友们有得出解法了的也欢迎留言告诉我哦。好了，今天就到这里了。

文章版权归作者所有，未经允许请勿转载。

THE END

后端