开发进行时...

java实现
不知道是否正确...

import java.util.Arrays;

public class PassRiver {

private int[] a = new int[]
{45,10,7,6,6,4,3,2,2};
//{400,500,501,502,5005,5008};
//{1,2,100,45,10,7,6,6,4};
//private int[] b = new int[a.length];

public void pass(){

if(a.length==1){
System.out.println("->速度为"+a[0]+"的人过河,时间为:"+a[0]);
return;
}
if(a.length==2){
System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为:"+(a[0]>a[1]?a[1]:a[1]));
return;
}
Arrays.sort(this.a);
int total =0;
int n = a.length-1;
System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为："+a[1]);
total+=a[1];
System.out.println("<-速度为"+a[0]+"的人回来,时间为："+a[0]);
total+=a[0];

for(int j=n;j>=2;j--){
if(j==2 ){
total=print(a[0],a[j],total);
}else if(a[j-1]<=(a[0]+a[1])){
total=print(a[0],a[j],total);
total=print(a[0],total);
}
else if(a[j-1]==a[1] ){
total=print(a[0],a[1],total);//b[j]=1;
total=print(a[0],total);
}
else{
total=print(a[j],a[j-1],total);//b[j]=1;b[j-1]=1;
total=print(a[1],total);
total=print(a[0],a[1],total);
total=print(a[0],total);
j--;
if(j==2){
total=print(a[0],a[1],total);
break;
}
}

}
System.out.println("total time:"+total);

}
private int print(int a,int total){
System.out.println("<-速度为"+a+"的人回来,时间为："+a);
return total+a;
}
private int print(int a,int b,int total){
System.out.println("->速度为"+a+"、"+b+"的人过河,时间为："+(a>b?a:b));
return total+(a>b?a:b);
}
public static void main(String[] args) {
PassRiver p = new PassRiver();
p.pass();

}
}

这样做不知道对不对：

假设按速度从大到小排序，其速度为 v[0]...v[n-1]
那么最快的方法应该是由 速度为 v[0] 的人 ( 称其为 p[0] ) 与 p[1]一起过河，然后 p[0] 将氧气瓶送回，再与 p[2] 一起过河...最后 p0 与 p[n-1] 一起过河
设河宽为 L ,那么 p[0] 往回游的时间为 (n-1)*L/v[0] ,而过河时间分别为 L/v[1], L/v[2], ..., L/v[n-1]
故总时间 (n-1)*L/v[0] + L/v[1] + L/v[2] + ... + L/v[n-1]

上面的JAVA程序中 速度为x的人过河，写错了，实为过河时间为X的人过河...

楼上的想法不对，如{45,10,7,6,6,4,3,2,2}

第一趟为:2，2过河，2回来
第二趟为:45,10过河，2回来(另一个2)

这样时间才是比较短的...

改了下程序

import java.util.Arrays;

public class PassRiver {

private int[] a = new int[]
//{1,2,4,5};
{45,10,7,6,6,4,3,2,2};
//{400,500,501,502,5005,5008};
//{1,2,100,45,10,7,6,6,4};
//private int[] b = new int[a.length];

public void pass(){

if(a.length==1){
System.out.println("->速度为"+a[0]+"的人过河,时间为:"+a[0]);
return;
}
if(a.length==2){
System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为:"+(a[0]>a[1]?a[1]:a[1]));
return;
}
Arrays.sort(this.a);
int total =0;
int n = a.length-1;

total = print(a[0],a[1],total);
total=print(a[0],total);
for(int j=n;j>=2;j--){
if(j==2 ){
total=print(a[0],a[j],total);
}else if(a[j-1]+2*a[0]<=a[1]){
total=print(a[0],a[j],total);
total=print(a[0],total);
}
else if(a[j-1]==a[1] ){
total=print(a[0],a[1],total);//b[j]=1;
total=print(a[0],total);
}
else{
total=print(a[j],a[j-1],total);//b[j]=1;b[j-1]=1;
total=print(a[1],total);
total=print(a[0],a[1],total);
total=print(a[0],total);
j--;
if(j==2){
total=print(a[0],a[1],total);
break;
}
}

}
System.out.println("total time:"+total);

}
private int print(int a,int total){
System.out.println("<-过河时间为"+a+"的人回来,时间为："+a);
return total+a;
}
private int print(int a,int b,int total){
System.out.println("->过河时间为"+a+"、"+b+"的人过河,时间为："+(a>b?a:b));
return total+(a>b?a:b);
}
public static void main(String[] args) {
PassRiver p = new PassRiver();
p.pass();

}
}

{45,10,7,6,6,4,3,2,2}输出的结果是：

->过河时间为2、2的人过河,时间为：2
<-过河时间为2的人回来,时间为：2
->过河时间为45、10的人过河,时间为：45
<-过河时间为2的人回来,时间为：2
->过河时间为2、2的人过河,时间为：2
<-过河时间为2的人回来,时间为：2
->过河时间为7、6的人过河,时间为：7
<-过河时间为2的人回来,时间为：2
->过河时间为2、2的人过河,时间为：2
<-过河时间为2的人回来,时间为：2
->过河时间为6、4的人过河,时间为：6
<-过河时间为2的人回来,时间为：2
->过河时间为2、2的人过河,时间为：2
<-过河时间为2的人回来,时间为：2
->过河时间为2、3的人过河,时间为：3
total time:83

以前听过类似的题，好像是尽量让速度差不多的人一起过去。

要是不算最短时间呢？而是展示所有的情况