赶牛过河
网络
2009-07-16 09:50:02
题目：牧童骑在牛背上赶牛过河，共有甲、乙、丙、丁4头牛。甲牛过河需1分钟，乙牛过河需2分钟，丙牛过河需5分钟，丁牛过河需6分钟。又知，每次只能赶两头牛过河。那么牧童要把这4头牛都赶到对岸最少要用几分钟？
分析与解：要使用的时间最少，我们首先得让牧童骑着用时最少的牛返回。所以
第一次，牧童赶甲、乙两头牛过河，用2分钟；然后骑甲回来，用1分钟。
第二次，牧童赶甲、丙两头牛过河，用5分钟；然后再骑甲回来，用1分钟。
第三次，牧童赶甲、丁两头牛过河，用6分钟。
这时四头牛全部过河，总共用了：2＋1＋5＋1＋6=15（分钟），是不是最省时呢？
其实不然，最短的时间是13分钟，先想一想这是为什么？
刚才我们只考虑回来的时间要最少，却将用时最多的两牛分开过河了。让用时最多的两牛同时过河，再骑用时较少的牛返回，不是更省时吗？
所以最优的方案应该是：
第一次，牧童赶甲、乙两牛过河，用2分钟；然后骑甲回来，用1分钟。
第二次，牧童赶丙、丁两头牛过河，用6分钟；然后骑乙牛回来，用2分钟。
第三次，最后赶甲、乙过河，用2分钟。
这次四头牛全部过河，只需用：2＋1＋6＋2＋2=13（分钟）
