首发于范浩博科学院服务目前每月评分搬家高手。根据高手排名结果，我们将优先保证最优秀的高手全天接单。假设师傅每天工作8小时，每天给定n个订单，每个订单占用时间$T_i$，赚取价值$V_i$，现在请师傅安排订单，保证师傅赚到的最大值。输入格式输入n组数据，每组之间用逗号隔开，每个订单的数量、时长、挣值用空格隔开。输出格式输出值和订单号。订单号按值从大到小排序，值相同。,然后按照每小时平均值从大到小排序例子：输入：[MV100012100,MV10008230,MV100031200,MV100096500,MV100103400]输出：730MV10010MV10003MV10001MV10000输入：[M1000012100,M100023210,M10003300,M100042150,M10005170,M10006220,M1000710,M10008330,M100093200,M100102400]输出:990m1problemm10001solving:990m150m10001每个订单每天只安排一次，这是一个典型的动态规划求解的01背包问题。动态规划概念动态规划过程：每个决策都依赖于当前状态，然后导致状态的转移。决策序列是在不断变化的状态下产生的，所以这种多阶段优化的决策过程称为动态规划。动态规划原理：动态规划类似于分治法。它将原始问题划分为不同尺度和相同特征的小问题。通过寻找特定的递归关系，先把小问题一个一个解决，最终达到解决原问题的效果。.建立动态方程假设，master获得最大值的顺序为$x_1$,$x_2$,$x_3$,...,$x_i$（其中$x_i$取1或0，表示第i-$v_i$表示第i个订单的值，$w_i$表示第i个订单的耗时，$wv(i,j)$表示第i个第-次订单排列完毕，master总共花费的时间为第j时刻的最大值。可以得到订单价值和时间消耗的关系：i12345w(i)22163v(i)10030200500400因此，可以得到动态方程：$$wv(i,j)=begin{cases}wv(i-1,j)(jgoods=$goods;$this->W=$c;$this->n=count($goods);//初始化项目值$v=array_column($goods,2);array_unshift($v,0);$this->v=$v;//初始化物品重量$w=array_column($goods,1);array_unshift($w,0);$this->w=$w;//初始化最大值$this->wv=array_fill(0,$this->n+1,array_fill(0,$this->W+1,0));$this->pd();$this->canPut();}publicfunctiongetMaxPrice(){return$this->wv[$this->n][$this->W];}}动态求解过程：publicfunctionpd(){for($i=0;$i<=$this->W;$i++){for($j=0;$j<=$this->n;$j++){//当没有放置物品且权重为空时，值为0if($i==0||$j==0){continue;}//决定if($i<$this->w[$j]){$this->wv[$j][$i]=$this->wv[$j-1][$i];}else{$this->wv[$j][$i]=max($this->wv[$j-1][$i],$this->wv[$j-1][$i-$this->w[$j]]+$this->v[$j]);}}}}求解过程：publicfunctioncanPut(){$c=$this->W;for($i=$this->n;$i>0;$i--){//当背包质量为c时，第i-1个和第i-1个物品的值保持不变，表示没有放置第一个物品if($this->wv[$i][$c]==$this->wv[$i-1][$c]){$this->goods[$i-1][3]=0；}else{$this->goods[$i-1][3]=1;$c=$c-$这个->w[$i];}}}获取订单信息，按订单价值降序排列（如果订单价值相同，则按单位时间平均值降序排列）：publicfunctiongetGoods(){$filter=function($value){return$值[3]；};$goods=array_filter($this->goods,$filter);usort($goods,function($a,$b){如果($a[2]==$b[2]){如果($a[2]/$a[1]<$b[2]/$b[1]){返回1;}返回0;}返回$a[2]<$b[2];});return$goods;}接收标准输入处理并输出结果：$arr=explode(',',$input);$filter=function($value){returnexplode('',$value);};$knapsack=newKnapsack(array_map($filter,$arr),8);$goods=$knapsack->getGoods();echo$knapsack->getMaxPrice(),'',implode('',array_column($goods,0)),PHP_EOL;综上所述，本题采用动态规划求解，算法时间复杂度为$O(nc)$。当然也可以用其他方法解决。例如，先将订单按价值排序，然后尝试依次排列订单。在剩余时间之前不能再下订单。动态规划的其他典型应用请参考动态规划常见问题分析与解决一文。相关文章?编程大赛之王之一（2017-12-05）编程大赛之王之二-水库（2017-12-05）编程之王之四-约瑟夫·林格（2017-12-06）王者编程大赛之一——最短路径(2017-12-06)
