算法设计与分析 课件 6.4-贪心法应用-过河问题.pptx

;一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸，过桥时必须借助灯光照明。

独木桥最多能承受两个人，由于只有一盏灯，因此过桥时间等于较慢的那个人单独过桥所需要的时间。

给定N个人(2=N1000)人单独过桥需要的时间，请计算最少需要多少时间，他们才能全部到达河左岸。;每个人的过河时间从小到大存储在t[i]中，i=0~n-1。

按照问题规模从小到大进行分析：

当n=1,2时，直接过河；

当n=3时，需要两趟；;按照问题规模从小到大进行分析：

当n=1,2,3时，容易求解；

当n较大时，把若干人送到对岸，再有人把灯拿回来，就可以转换为规模更小的过河问题。

基于用时最少的要求，选择过河时间较快的人把灯拿回来。;按照问题规模从小到大进行分析。

当n=1,2,3时，容易求解；

当n≥4时，将过河所需时间最多的两个人送到河对岸，有两种方式：;贪心法求解过河问题的步骤：

按从小到大的顺序对过河时间排序，存储到数组t中；

当n=4时，比较方式一和方式二的时间，选择用时少的（贪心选择策略），同时n=n-2；

重复步骤2，直到人数不足4时，直接求解。;sort(t,t+num);/*对过河时间从小到大排序*/

voidwork(intn)/*贪心法求解n个人的过河问题*/

{

if(n==1){ans+=t[0];return;}

if(n==2){ans+=t[1];return;}

if(n==3){ans+=t[0]+t[1]+t[2];return;}

if(n=4){

if((t[1]*2)=(t[0]+t[n-2]))

ans+=t[0]*2+t[n-2]+t[n-1];/*选择方式一*/

else

ans+=t[1]*2+t[0]+t[n-1];?/*选择方式二*/

work(n-2);/*递归调用*/

return;

}

}