之所以会这样，是因为我们公司举办了一次算法编程大赛，随机抽签下图的算法题目。那就是动态规划中的“背包问题”。背包问题是组合优化的NP完全问题。问题可以描述为：给定一组物品，每件物品都有自己的重量和价格，在有限的总重量内，我们如何选择才能使物品的总价格最高。如何选择最合适的物品放在给定的背包里，这与我们的主题是一致的，所以这次我们使用“0-1背包问题”来代替我们这次的主题。“总人数”相当于“背包”，“物品”相当于“工单类型”，物品的重量就是需要的人数。补充：背包问题求解的扩展有3种：无界背包问题、0-1背包问题、二次背包问题（不做详细扩展，直接用）。算法题目如下。动态规划处理的问题是一个多阶段决策问题，一般从初始状态开始，通过中间阶段决策的选择到达结束状态。这些决策形成一系列决策，同时确定一个行动方案（通常是最佳行动方案）来完成整个过程。动态规划的设计有一定的规律，一般要经过以下几个步骤。初始状态→│决策1│→│决策2│→…→│决策n│→结束状态动态规划公式：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）up一个工单类型对应的技术人员数量，工单利润P(n,m)==>(决策2)当前工单类型对应的技术人员数量，工单利润f(n-1,m-w[n])==>减去当前工单需要的人数，以及之前决策对应人数的利润，所以最优解的答案是：五个技术人员对应的值在decisionn，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][数量]:10carDetail[3][类型]:空调专项检测解决方法一：动态规划$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);如果（$prevGain>$nowTotalGain）{$cacheMapName[$j][$i]=$prevName;}else{$cacheMapName[$j][$i]=$name.'+'.$surplusName;}}}}$actual=count($postData['carDetail']);返回['maxMatch'=>$cacheMap[$actual][$totalPeople],'maxMatchName'=>trim($cacheMapName[$actual][$totalPeople],'+')];}}$bestMatch=newbestMatch;if(empty($_POST)||isset($_POST['people'])&&$_POST['people']>0){die('提交参数错误');}$res=$bestMatch->getMethod($_POST);$t2=microtime(true);echo'动态规划：'.'
';echo'最佳量：'.$res['maxMatch'].'
';echo'最佳包匹配：'.$res['maxMatchName'].'
';echo'耗时'.round($t2-$t1,7).'秒'.'
';echo'内存消耗：'.memory_get_usage().'wordSection'.'
';方案二：递归0){$value['name']=$up['name'].'+'.$array[$i]['type'];$value['amount']=bcadd($up['amount'],$array[$i]['amount']);$value['技术员']=bcadd($up['技术员'],$array[$i]['技术员']);}else{$value['name']=$array[$i]['type'];$值['金额']=bcadd($数组[$i]['金额'],0);$value['技术员']=bcadd($array[$i]['技术员'],0);}$结果[]=$值；$this->getSortList($array,$i+1,$value,$result);}返回$结果;}publicfunctiongetMethod($postData){$people=$postData['people'];$carDetail=$postData['carDetail'];$allResult=$this->getSortList($carDetail);$最佳匹配=[];foreach($allResultas$val){if($val['technician']<=$people){if($bestMatch){if($val['amount']>$bestMatch['amount']){$最佳匹配=$val;}}else{$bestMatch=$val;}}}返回$bestMatch;}}$optimal=newoptimal();if(empty($_POST)||isset($_POST['people'])&&$_POST['people']>0){die('提交参数错误');}$bestMatch=$optimal->getMethod($_POST);$t2=microtime(true);echo'递归查询：'.'
';echo'最佳数量：'.$bestMatch['amount'].'
';echo'最佳包匹配：'.$bestMatch['name'].'
';echo'耗时'.round($t2-$t1,7).'Seconds'.'
';echo'内存消耗：'.memory_get_usage().'Bytes'.'
';参考文章链接：书籍：算法图https://blog.51cto.com/chinal...
