Question

河的左岸有4艘船，橫渡到對岸的時間分別為：A需要2分鐘，B需要4分鐘，C需要8分鐘，D需要16分鐘．目前只有一位船夫，一條船的后面可以再拴一條船，而且此時渡河所費時間為拴在一起的兩條船中較慢那條船所用的時間．現(xiàn)在船夫每次用一條船牽一條船渡河到右岸，然后再開一條船回到左岸．如此反復，直到把所有的船都開到右岸，請問最少需要多少時間？（換船和拴船的時間忽略不計）

Answer 1

考點：最佳方法問題

專題：優(yōu)化問題

分析：首先一次可以把兩條船送過對岸，只有一位船夫，必須返回來送第二次，現(xiàn)在這邊有3條船，第二次只能送2條船，所以還需要返回1次，第三次只有2條船，不用返回了，所以至少送3次，兩個返回，所以首先讓需要時間短A、B的船先到到對岸，返回時盡量用需要時間少的船A（或B），然后把C、D送過去，用B（或A）返回，最后把A、B送過對岸，即可得解．

解答： 解：①A和B到右岸，需要4分鐘．A返回，需要2分鐘；
②C和D到右岸，需要16分鐘．B返回，需要4分鐘；
③A和B到右岸，需要4分鐘．
一共：4+2+16+4+4=30（分鐘）
答：最少需要30分鐘時間．

點評：明白至少送3次返回2次，盡量2次返回的時間最少是解決此題的關鍵．