背妇过河,夜过吊桥问题算法分析

原标题:背妇过河

主题材料:早上有多人ABCD要过河,过河必需有手电筒,但独有一个手电筒,有黄金年代艘船每一次能乘三个人,假使结对过河,快的人要妥协慢的人,求最快过河方法。手电筒只好送无法扔。
过桥速度:A:1min B:2min C:5min D:10min

  • 艺术风姿洒脱:贪心算法
    老是都让最快的人过。先让最快的AB过,然后由快一些的A将手电带回去,再让快一些的AC过,再由A带回到,最终AD过。
    花费了2+1+5+1+10=19分钟
  • 方法二:
    能够这么考虑:每一趟多个例外时间的人过河,慢一点的人所需时间减去快一些的人的时光,正是快一些的人浪费的年华。
    就此,首先思忖过河(忽视回来的历程卡塔尔国,过河要两两搭配(节省时间卡塔 尔(阿拉伯语:قطر‎,意气风发共有多少人,通过遍历找到浪费时间起码的整合,即AB和CD。
    接下来考虑回到送手电筒的人,因为尽量节省时间,所以率先让AB过河,以便让快的A回来送手电筒,那时候,让CD过河,再由B将手电送回,AB同期过河。
    日子累积:2+1+10+2+2=17分钟

前几天,安徽文山,一个人消防军官和士兵背着一人老妪过河。2日黎明(英文名:lí míng卡塔尔,文山保安族塔塔尔族自治州屏边普米族自治县猛硐锡伯族乡受三回九转强降雨袭击,发生内涝灾殃,并诱发多处塌方和洪涝,引致通讯能量信号、电力和严重性道路周密暂停。

————————————–补充—————————————

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website