过桥问题的贪心解法

2019-03-29 本文已影响0人 siriusing

过桥问题：

黑夜，只有一只手电筒
A过桥需要1s
B过桥需要3s
C过桥需要5s
D过桥需要8s
E过桥需要12s
求最小过桥时间

贪心算法：

从最大的开始过去，最小的两个做为辅助。

image.png

综上，此时

$T= \begin{cases} A_i+A_j & \text{j-i<2} \\ A_i+A_{i+1}+A_{i+2} & \text{j-i<3}\\ max(2A_i+A_{j-1}+A_j,A_i+2A_{i+1}+A_j) & \text{other}\\ \end{cases}$

tips: 记得每次j-2。

代码略。