求配货组合的最优算法

Question

假设商品编码如下： Array (     [0] => A     [1] => B     [2] => C     [3] => D     [4] => E     [5] => F     [6] => G     [7] => H     [8] => I     [9] => J     [10] => K     [11] => L     [12] => M     [13] => N     [14] => O ) 商品库存： Array (     [A] => 34     [B] => 37     [C] => 27     [D] => 25     [E] => 45     [F] => 24     [G] => 37     [H] => 40     [I] => 49     [J] => 34     [K] => 49     [L] => 23     [M] => 44     [N] => 31     [O] => 22 ) 100个用户申请发货，至少两件商品才可以申请发货，发货清单如下 Array (     [0] => HII     [1] => ACDI     [2] => AG     [3] => AD     [4] => DG     [5] => ADDFG     [6] => BGI     [7] => DDFGI     [8] => AACEJ     [9] => ABC     [10] => ABD     [11] => AABF     [12] => BFGJ     [13] => CEGHI     [14] => AEFFF     [15] => AFGH     [16] => EH     [17] => CE     [18] => AD     [19] => FHHIJ     [20] => BDDHJ     [21] => CEFJJ     [22] => AB     [23] => CH     [24] => ACEJ     [25] => ABC     [26] => HI     [27] => AAEFIJ     [28] => ADII     [29] => BFFJ     [30] => DDHHJ     [31] => EGJJ     [32] => DG     [33] => AAABFH     [34] => BJ     [35] => CG     [36] => CI     [37] => FG     [38] => FFGGJJ     [39] => CFFH     [40] => BDFF     [41] => CDFH     [42] => DEG     [43] => ACEG     [44] => CGI     [45] => AEEI     [46] => AACFGH     [47] => FGG     [48] => ACDFHJ     [49] => ABHH     [50] => CDIIJ     [51] => BCD     [52] => AEFHHI     [53] => EEEH     [54] => AACEFH     [55] => DDEGHJ     [56] => GHJJJ     [57] => BEFJJ     [58] => DEHIJJ     [59] => ABDJ     [60] => BE     [61] => BEEGGI     [62] => AFJ     [63] => FF     [64] => AE     [65] => ABEJ     [66] => AIJJ     [67] => AE     [68] => CHJ     [69] => ACHII     [70] => AAEFGJ     [71] => FG     [72] => AEH     [73] => EF     [74] => EG     [75] => EGHI     [76] => DFG     [77] => ABDHI     [78] => BDE     [79] => EEGIJJ     [80] => AAADGG     [81] => FFF     [82] => AI     [83] => ACEFJ     [84] => AACDEF     [85] => EEGIIJ     [86] => BF     [87] => AD     [88] => BEJJ     [89] => DDEEFF     [90] => BFGII     [91] => BDDE     [92] => BCCDIJ     [93] => AACCCH     [94] => AABFG     [95] => CDHIJ     [96] => BCDEGJ     [97] => DEHJ     [98] => EFG     [99] => BEEFI ) 求已知上述商品库存的情况下，可以发出的最大包裹数是多少

Answer 1

<?php
# 以下纯属个人见解，算法或许不是最优，欢迎各位大佬点评
# 商品数组
$goods = array('A','B','C');
# 商品库存数组
$store = array('A' => 4, 'B' => 3, 'C' => 2);
$tmp = []; # 记录商品添加的次数
$result = []; # 表示各种组合
# i 表示最少几个商品组合
for ($i = 2 ;$i <= 4 ; $i ++  ){
    $combines    = Combination($goods,$i);
    $result = array_merge($result,$combines);
}
# 反转，键从小到大的商品为 最多组合的商品 到 最少商品的组合
$result = array_reverse($result);
# 验证库存
foreach ($result as $key => $item){
    $flag = false; # 表示是否删除此项
    $com = explode('---',$item);
    foreach ($com as $v){
        if(in_array($v,array_keys($tmp))){
            if($tmp[$v] >= $store[$v]) {
                $flag = true;
                continue;
            } else {
                $tmp[$v] += 1;
            }
        } else {
            $tmp[$v] = 1;
        }
    }
    if($flag) unset($result[$key]);
}

/*从数组中拿出组合数*/
function Combination($sort, $num)
{
    $result = $data = array();
    if( $num == 1 ) {
        return $sort;
    }
    foreach( $sort as $k=>$v ) {
        unset($sort[$k]);
        $data   = Combination($sort,$num-1);
        foreach($data as $row) {
            $result[] = $v.'---'.$row;
        }
    }
    return $result;
}