这道题的关键是两个人同时过桥时,时间按照速度慢的那个人算,而且必须有一个人返回把灯给送回来,所以可以采用下面的方法:
1姐姐和弟弟先过,用时3分钟,
弟弟返回,用时1分钟,把灯送回
2父亲和爷爷再过,用时12分钟,
姐姐返回,用时3分钟,把灯送回
3弟弟和妈妈再过,用时6分钟,
弟弟返回,用时1分钟,把灯送回
4弟弟和姐姐再过,用时3分钟,
总共用时:1+3+12+3+6+1+3=29分钟
以下是构造N个人(N >= 1)过桥最佳方案的方法:
1)如果N=1或者N=2,所有人直接过桥。
2)如果N=3,由最快的人往返一次把其他两人送过河。
3)如果N>=4,设A,B为走的最快的和次快的旅行者,过桥所需时间分别为a,b;而Z,Y为走得最慢的和次慢的旅行者,过桥所需时间分别为z,y。那么
当2b>a+y时,使用模式一将Z和Y移动过桥
当2b当2b=a+y时,使用模式一或者模式二将Z和Y移动过桥。
这样问题就变成了N-2个旅行者的情形,递归解决即可。
注:这里的模式1指的是A将Z送过桥,然后返回,再把Y送过桥,再返回;模式2指的是A和B先过桥,然后A返回,Y和Z过桥,然后B返回
1、先由姐姐和弟弟过桥。弟弟带回灯时间3+1=4分钟
2、爷爷和父亲过桥,姐姐带回灯12+3=15钟。
3、弟弟和妈妈过桥,弟弟带回灯6+1=7分钟,
4、姐姐和弟弟过桥,3分钟,
总共时间4+15+7+3=29分钟。
去:1,3 =3
回:1 =1 (1 6 8 12 | 3
去:8,12 =12
回:3 =3 (1 3 6 | 8 12
去:1,6 =6
回:1 =1 (1 3 | 6 8 12
去:1,3=3
共用时3+1+12+3+6+1+3=29
1 笨重爸和弟弟过桥及弟弟返回 9分钟
2 敏捷妈背弟弟和行动不便爷过桥及弟弟返回 13分钟
3 姐姐和弟弟过桥 3分钟
共25分钟