动态规划——车队过桥

《动态规划——车队过桥》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划-车队过桥〖题目描述〗GDOI工作组遇到了一个运输货物的问题。现在有N辆车要按顺序通过一个单向的小桥，由于小桥太窄，不能有两辆车并排通过，所以在桥上不能超车。另外，由于小桥建造的时间已经很久，所以小桥只能承受有限的重量，记为Max（吨）。所以，车辆在过桥的时候必须要有管理员控制，将这N辆车按初始顺序分组，每次让一个组过桥，并且只有在一个组中所有的车辆全部过桥以后才让下一组车辆上桥。现在，每辆车的重量和最在速度是已知的，而每组车的过桥时间由该组中速度最慢的那辆车决定。现在请你编一个程序，将这N辆车分组，使得全部车辆通过小桥的时间最短。输入格式：数据存放在当前目录下

2、的文本文件“bridge.in”中。文件的第一行有三个数，分别为Max（吨），Len（桥的长度，单位：Km），N（三个数之间用一个或多个空格分开）。接下来有N行，每行两个数，第i行的两个数分别表示第i辆车的重量（吨）和最大速度（m/s）。注意：所有的输入都为整数，并且任何一辆车的重量都不会超过Max。输出格式：答案输出到当前目录下的文本文件“bridge.out”中。文件只有一行，输出全部车辆通过小桥的最短时间（s），精确到小数点后一位。输入输出样例：bridge.inbridge.out10051040255020701012509704930382527501970

3、75.0〖参考程序〗programbridge;usescrt;vara:array[0..1000]ofreal;b:array[1..1000,1..2]oflongint;max,len,n:longint;c:longint;f1,f2:Text;proceduretry;varc,d,e,f,g:longint;flag:boolean;time,t,t1:real;begina[0]:=0;a[1]:=(len/b[1,2]);forc:=2tondobeginflag:=true;d:=c+1;e:=0;f:=maxint;time:=maxint;whi

4、leflagdobegind:=d-1;if(e+b[d,1])<=maxthenbegine:=e+b[d,1];ifb[d,2]

5、n(f2,'bridge1.out');reset(f1);readln(f1,max,len,n);forc:=1tondoreadln(f1,b[c,1],b[c,2]);close(f1);try;end.