求配货组合的最优算法

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; }