有四個人 一個手電筒
現在要過一個山洞 但每次最多只能兩個人一起用一個手電筒過山洞
現在這四個人過三洞所要花的時間各為 1 2 4 6
求四個人要完全過完山洞最少需多久
(若可以的話 請說明為何是最短的)
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: arist.m7.ntu.edu.tw
> -------------------------------------------------------------------------- <
作者: thalesf (家有HBO真好) 看板: puzzle
標題: Re: 過山洞問題(300ptt幣)
時間: Sat May 27 11:30:54 2000
※ 引述《arist (這實在是太複雜了)》之銘言：
: 有四個人 一個手電筒
: 現在要過一個山洞 但每次最多只能兩個人一起用一個手電筒過山洞
: 現在這四個人過三洞所要花的時間各為 1 2 4 6
: 求四個人要完全過完山洞最少需多久
: (若可以的話 請說明為何是最短的)
因為最多一次兩個人過去,所以總共至少要過去三次回來兩次
如果要讓時間最短,就必須要讓4,6一起走過去
如果4,6的是第一梯次走過去,那麼回來的時候就會花費多餘的時間
如果最後一梯次走過去,那麼前一次走回來的人就必定是4or6
所以只有在第二梯次走過去才會讓時間最短
走法如下:
第一梯次--1,2過去 1(2)回來
第二梯次--4,6過去 2(1)回來
第三梯次--1,2過去
總共要花13
上面的敘述好像不是很嚴謹,請多多指教#^^
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: h20.s155.ts32.hinet.net