服务目前每月会对搬家师傅进行评级,根据师傅的评级排名结果,我们将优先保证最优师傅的全天订单。
假设师傅每天工作 8 个小时,给定一天 n 个订单,每个订单其占用时间长为 $T_i$,挣取价值为 $V_i$,现请您为师傅安排订单,并保证师傅挣取价值最大。
输入格式
输入 n 组数据,每组以逗号分隔,并且每一个订单的编号、时长、挣取价值以空格分隔
输出格式
输出争取价值和订单编号,订单编号按照价值由大到小排序,争取价值相同,则按照每小时平均争取价值由大到小排序
示例:
输入:[MV10001 2 100,MV10008 2 30,MV10003 1 200,MV10009 6 500,MV10010 3 400]
输出:730 MV10010 MV10003 MV10001 MV10008
输入:[M10001 2 100,M10002 3 210,M10003 3 300,M10004 2 150,M10005 1 70,M10006 2 220,M10007 1 10,M10008 3 30,M10009 3 200,M10010 2 400]
输出:990 M10010 M10003 M10006 M10005
解题思路
由于本题每个订单每天只被安排一次,是典型地采用 动态规划 求解的 01 背包问题。
动态规划概念
动态规划过程:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划原理:动态规划与分治法类似,都是把原问题拆分成不同规模相同特征的小问题,通过寻找特定的递推关系,先解决一个个小问题,最终达到解决原问题的效果。
建立动态方程
假设,师傅挣取价值最大时的订单为 $x_1$,$x_2$,$x_3$,…,$x_i$(其中 $x_i$ 取 1 或 0,表示第 i 个订单被安排或者不安排),$v_i$ 表示第 i 个订单的价值,$w_i$ 表示第 i 个订单的耗时时长,$wv(i,j)$ 表示安排了第 i 个订单,师傅总耗时为 j 时的最大价值。
可得订单价值和耗时的关系图:
i | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
w(i) | 2 | 2 | 1 | 6 | 3 |
v(i) | 100 | 30 | 200 | 500 | 400 |
因此,可得 动态方程:
$$wv(i,j) = \begin{cases}
wv(i-1,j)(j < w(i)) \
max(wx(i-1,j),wv(i-1,j-w(i))+v(i))(j \geq w(i))
\end{cases}$$
说明:$j<w(i)$ 表示订单不被安排,$j \geq w(i)$ 表示订单被安排。
确定边界
可以确定边界条件 $wx(0,j) = wx(i, 0) = 0$,$wx(0,j)$ 表示一个订单都没安排,再怎么耗时价值都为 0,$wx(i,0)$ 表示没有耗时,安排多少订单价值都为 0。
求解
求解过程,可以填表来进行模拟:
- 如 i=1,j=1 时,有 $j<w(i)$,故 $wx(1,1) = wx(1-1,1) = 0$;
- 又如 i=1,j=2 时,有 $j=w(i)$,故 $wx(1,2) = max(wx(1-1,1), wx(1-1,2-w(1)) + v(1) = 100$;
- 如此下去,直至填到最后一个,i=5,j=8 时,有 $j<w(i)$,故 $wx(5,8) = max(wx(5-1,8), wx(5-1,8-w(5)) + v(5) = 730$;
- 在耗时没有超过 8 小时的前提下,当前 5 个订单都被安排过时,$wx(5,8) = 730$ 即为所求的最大价值;
解的组成
尽管 求解 过程已经求出了最大价值,但是并没有得出哪些订单被安排了,也就是没有得出解的组成部分。
但是在求解的过程中不难发现,寻解方程满足如下定义:
$$x(i) = \begin{cases}
wv(i,j) = wv(i-1,j) \
wv(i,j) \neq wv(i-1,j)
\end{cases}$$
从表格右下到左上为寻解方向,寻解过程如下:
- i=5,j=8 时,有 $wv(5,8) != wv(4,8)$,故 $x(5) = 1$,此时 $j -= w(5)$,$j = 5$;
- i=4 时,无论 j 取何值,都有 $wv(4,j) == wv(3,j)$,故 $x(5) = 0$,此时 $j = 5$;
- i=3,j=5 时,有 $wv(3,5) != wv(2,5)$,故 $x(3) = 1$,此时 $j -= w(3)$,$j = 4$;
- i=2,j=4时,有 $wv(2,4) != wv(1,4)$,故 $x(2) = 1$,此时 $j -= w(2)$,$j = 2$;
- i=1,j=2时,有 $wv(1,2) != wv(1,2)$,故 $x(1) = 1$,此时 $j -= w(1)$,$j = 0$,寻解结束;
编码实现
实现的代码如下,并将一一详细说明。
class Knapsack |
动态求解过程:
public function pd() |
寻解过程:
public function canPut() |
按照订单价值降序获取订单信息(若订单价值相同则按单位时间平均价值降序排列):
public function getGoods() |
接收标准输入处理并输出结果:
$arr = explode(',', $input); |
总结
该题使用动态规划求解,算法的时间复杂度为 $O(nc)$,当然也可以采用其他方式求解。例如先将订单按照价值排序,然后依次尝试进行安排订单,直至剩余耗时不能再被安排订单。
有关动态规划的其他典型应用,请参考 常见的动态规划问题分析与求解 一文。
相关文章 »
- 王者编程大赛之一 (2017-12-05)
- 王者编程大赛之二 — 蓄水池 (2017-12-05)
- 王者编程大赛之四 — 约瑟夫环 (2017-12-06)
- 王者编程大赛之五 — 最短路径 (2017-12-06)