过桥问题之——信使模型

最近看动态规划，发现经典的过桥问题，描述如下：
【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

*解法解析（摘引）

每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。

具体步骤是这样的：

• 第一步：1和2过去，花费时间2，然后1回来（花费时间1）；
• 第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；
• 第三步：1和2过去，花费时间2，总耗时17。

使用传统动态规划方法，可以参考https://blog.csdn.net/u013309870/article/details/75193592

思考：

通过上面的分析，其实这个问题可以这么理解，由于每次过桥必须有人陪同，那么陪同的人当然是时间越短越好，假设每个人过桥时间排序之后，最短的两个为a1,a2。
为了节约时间，我假设需要有个拿手电筒的信使，用来帮助将手电筒送回，这也很容易理解，为了尽量减少返程送手电筒的时间。那么我们就可以这么处理：
假设a1为主人（安排全局，因为他最快），a2就是a1主人养的信使，专门用来送手电筒，好了，下面介绍过程：

• 1）如果河对岸没有a2，那么这次主人a1一定要先把a2送过去，因为没有a2谁给你送回手电筒啊，所以这种情况下消耗 的时间为a2+a1（去程+回程），回程当然是主人带手电筒回来了，他最快啊
• 2）如果河对岸有a2，那么这次就不是主人去送人过去了，因为他送的话就只能送过去一个慢的人，效率不高，所以这个时候要让剩下的次慢和次次慢的两个人过去，消耗的时间就是次次慢的时间，两个人过去之后，让信使a2把手电筒送回，消耗时间为ai2+a2，（ai2为次次慢那个人的时间）

那么假设时间为 a1， a2， a3， a4，总时间为
（a2+a1）+（a4+a2）+（a2 + 0），本题中，带入时间为（1+2）+（2+10）+（2+0）=17

如果人数为奇数，时间为a1， a2， a3， a4，a5，总时间为
（a2+a1）+（a2+a4）+（a2 + a1）+（a5+0）