学历小助手
快速提升学历攻略、最新成考、自考、网络、全日制政策一手掌握~
发布时间: 2024年12月23日 09:21
过桥问题是统筹规划问题中的一种，合理安排进程使所需时间最少的问题，类型是几个人想要过桥，分别需要不同的时间.因为天黑，必须借助于手电筒过桥，可是他们总共只有一个手电筒，并且桥的载重能力有限，每次最多过两个人.怎样安排过桥顺序，使过桥时间最短的问题.
甲、乙、丙、丁四个人过桥，分别需要1分钟，2分钟，5分钟，10分钟.因为天黑，必须借助于手电筒过桥，可是他们总共只有一个手电筒，并且桥的载重能力有限，最多只能承受两个人的重量，也就是说，每次最多过两个人.现在希望可以用最短的时间过桥，怎样才能做到最短呢？你来帮他们安排一下吧.最短时间是多少分钟呢？
解决这类问题需要注意三点要求
1、所需时间相近的人分一组；
2、让速度快的人承担往返送手电筒的任务；
3、所需时间少的一组先过桥，再分别回来送手电筒.
如例题中，让甲、乙搭配，丙、丁搭配比较节省时间.让甲和乙先过桥，用时2分钟，再由甲返回送手电筒，需要1分钟，然后丙、丁搭配过桥，用时10分钟.接下来乙返回，送手电筒，用时2分钟，再和甲一起过桥，又用时2分钟.所以花费的总时间为：2+1+10+2+2=17分钟.
温馨提示：