事情原由
由于我司举办一个算法编程大赛，随机抽签下面图片的算法题目，想了一段时间记起之前在书（算法图解）上有一个算法比较符合，那就是动态规划中的“背包问题”。
背包问题(knapsack problem)是一种组合优化的np完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
如何选择最合适的物品放置于给定背包中，与我们的题目相符合，所以这次我们使用的是“0-1背包问题”，用我们这次的题目进行代入，“总人数” 等价于 “背包”，“物品” 等价于 “工单类型”，物品的重量就是所需人数。
补充：
背包问题解法延伸问题有三个：无界背包问题、0-1背包问题、二次背包问题 （不做详细延伸，只需我们使用的）
算法题目如下
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
动态规划解题公式:
f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+p(n,m)}
● 横向m(总人数),纵向n(4辆车做的工单类型)
● f(n-1,m) ==> (决策1)上一个工单类型对应的技师人数，做的工单利润
● p(n,m) ==> (决策2)当前工单类型对应的技师人数，做的工单利润
● f(n-1,m-w[n]) ==> 用减去当前工单所需人数，在上一个决策中对应人数的利润
所以最优解的答案是：决策n中五个技师中对应的值，1799元
postman提交参数：
people:5cardetail[0][technician]:2cardetail[0][amount]:49cardetail[0][type]:全车安检cardetail[1][technician]:2cardetail[1][amount]:499cardetail[1][type]:深度诊断cardetail[2][technician]:3cardetail[2][amount]:1300cardetail[2][type]:二手车检测cardetail[3][technician]:1cardetail[3][amount]:10cardetail[3][type]:空调专项检测
解答方式一：动态规划
<?php// 动态规划error_reporting(e_all ^ e_notice);$t1 = microtime(true);class bestmatch{ public function getmethod($postdata) { $peoplearr = $gainarr = $namearr = [0]; foreach ($postdata['cardetail'] as $val) { // 初始化各个套餐：所需人数、利润和套餐名称数组 $peoplearr[] = $val['technician']; $gainarr[] = $val['amount']; $namearr[] = $val['type']; } // 获取人数总数（背包） $totalpeople = $postdata['people']; // 做检测单数 $items = count($peoplearr); // 利润列表 - 初始状态 $cachemap[] = array_fill(1, $items, 0); // 套餐列表 - 初始状态 $cachemapname[] = array_fill(1, $items, ''); //中间的各种决策(依次放入物品a,b,c,d,e) // 第一个循环是总人数 for($i = 1; $i <= $totalpeople; $i++) { // 第二个循环是套餐 for($j = 1; $j < $items; $j++) { $requiredpeople = $peoplearr[$j]; $gain = $gainarr[$j]; $name = $namearr[$j]; // 上一行坐标数 $preline = $j-1; $prevgain = $cachemap[$preline][$i]; $prevname = $cachemapname[$preline][$i]; if($requiredpeople > $i) { $cachemap[$j][$i] = $prevgain; $cachemapname[$j][$i] = $prevname; } else { // 剩余价值 if ($i-$requiredpeople >= 0) { $surpluspeople = $i-$requiredpeople; $surplusgain = $cachemap[$preline][$surpluspeople]; $surplusname = $cachemapname[$preline][$surpluspeople]; }else { $surplusgain = 0; $surplusname = ''; } $nowtotalgain = $gain + $surplusgain; $cachemap[$j][$i] = max($prevgain, $nowtotalgain); if ($prevgain > $nowtotalgain) { $cachemapname[$j][$i] = $prevname; }else{ $cachemapname[$j][$i] = $name.'+'.$surplusname; } } } } $actual = count($postdata['cardetail']); return [ 'maxmatch' => $cachemap[$actual][$totalpeople], 'maxmatchname' => trim($cachemapname[$actual][$totalpeople],'+') ]; }}$bestmatch = new bestmatch;if (empty($_post) || isset($_post['people']) && $_post['people'] > 0) { die('提交参数有误');}$res = $bestmatch->getmethod($_post);$t2 = microtime(true);echo '动态规划: '.'<br/>';echo '最佳金额: '.$res['maxmatch'].'<br/>';echo '最佳套餐搭配: '.$res['maxmatchname'].'<br/>';echo '耗时'.round($t2-$t1,7).'秒'.'<br/>' ;echo '消耗内存: ' . memory_get_usage().'字节'.'<br/>' ;
解答方式二：递归
<?php// 递归查询error_reporting(e_all ^ e_notice);$t1 = microtime(true);class optimal{ public function getsortlist($array,$index = 0,$up =0,&$result =[]) { for ($i=$index; $i < count($array); $i++) { if($index > 0 ){ $value['name'] = $up['name'].'+'.$array[$i]['type']; $value['amount'] = bcadd($up['amount'],$array[$i]['amount']); $value['technician'] = bcadd($up['technician'],$array[$i]['technician']); }else{ $value['name'] = $array[$i]['type']; $value['amount'] = bcadd($array[$i]['amount'],0); $value['technician'] = bcadd($array[$i]['technician'],0); } $result[] = $value; $this->getsortlist($array,$i+1,$value,$result); } return $result ; } public function getmethod($postdata) { $people = $postdata['people']; $cardetail = $postdata['cardetail']; $allresult = $this->getsortlist($cardetail); $bestmatch = []; foreach ($allresult as $val) { if ($val['technician'] <= $people) { if ($bestmatch) { if ($val['amount'] > $bestmatch['amount']) { $bestmatch = $val; } }else{ $bestmatch = $val; } } } return $bestmatch; }}$optimal = new optimal();if (empty($_post) || isset($_post['people']) && $_post['people'] > 0) { die('提交参数有误');}$bestmatch = $optimal->getmethod($_post);$t2 = microtime(true);echo '递归查询: '.'<br/>';echo '最佳金额: '.$bestmatch['amount'].'<br/>';echo '最佳套餐搭配: '.$bestmatch['name'].'<br/>';echo '耗时'.round($t2-$t1,7).'秒'.'<br/>' ;echo '消耗内存: ' . memory_get_usage().'字节'.'<br/>' ;
以上就是php实现动态规划之背包问题的详细内容。