java中经典算法问题之过河的案例

java中经典算法问题之过河的案例？这个问题可能是我们日常学习或工作经常见到的。希望通过这个问题能让你收获颇深。下面是小编给大家带来的参考内容，让我们一起来看看吧！

描述

一群N人希望用一条船过河，这条船最多只能载两个人。因此，必须安排某种穿梭安排，才能来回划船，以便所有人都能过关。每个人都有不同的划船速度；一对选手的速度取决于速度较慢的人的速度。你的工作是确定一个策略，尽量减少这些人的过河时间。
输入

输入的第一行包含一个整数T(1<=T<=20)，测试用例数。接下来是T个案例。每个案例的第一行包含N，第二行包含N个整数，给出每个人过河的时间。每个案例前面都有一个空白行。不会有超过1000人，没有人需要超过100秒的跨越。
输出量

对于每个测试用例，打印一行，其中包含所有N个人过河所需的总秒数。
样本输入

1
4
1 2 5 10
样本输出

17

------------------------------------------------------------------------------------------------------------------------------

问题分析
（以下N人速度分别用abcd…表示，且按速度升序排序）

1. 当n=1时，time则为a
2. 当n=2时，time则为b
3. 当n=3时，time则为a+b+c（a与任意一个人过河，a再回来，再和剩下的人过河）
4. 当n>= 4 时，问题就复杂很多，因为任意两人过河，再在过了河中其中一个再回来有很多情况，我们这里需要进行分析
   观察题目我们可以发现过河中有两个最为重要的点
   方案【1】过河的两个人，花费时间是由最长的人决定
   针对这一点，我们可以把最慢d的和次慢c的放一起，这样次慢的时间c就被忽略。
   方案【2】回来的一个人，花费时间只由他一个人决定
   针对这一点，我们可以让最快的a把其他人一一送过去，再由最快的a把船送回来

将上面的方案实现
当n=4时（以下N人速度分别用abcd…表示，且按速度升序排序）（）内表示花费时间
方案【1】abcd
ab（b）过去
a （a）回来
cd（d）过去
b（b）回来
ab（b）过去
所花费时间：a+3b+d

方案【2】abcd
ad（d）过去
a（a）回来
ac（c）过去
a（a）回来
ab（b）过去
所花费时间：2a+b+c+d

计算样例
现在我们导入题目样例{1，2，5，10}
方案【1】时间=17
方案【2】时间=19
所以用方案【1】花费时间最短，时间为17

但如果我们修改一下数据{1，2，2，10}
方案【1】时间=17
方案【2】时间=16
这次却是方案【2】花费的时间最短，时间为16；

如果我们将两个方案的所花费时间约一下则
方案【1】：2b
方案【2】：a+c
可以看出所花费的时间 决定性因素 在于最快的a和次快的b和次慢的c，我们只需要将2b和a+c进行比较，选择花费时间最小的方案即可。

当n> 4时我们可以表示为用最快的前两个人运送最慢的后两个人便可,运送完人数就减少2 .

进口java.util.Arrays;
　　进口java.util.Scanner;
　　
　　公开课过河
　　{
　　静态长时间=0 l;
　　公共静态void main (String [] args)
　　{
　　扫描仪sc=new扫描仪(系统);
　　int m=sc.nextInt ();
　　for (int i=0;我& lt;m;我+ +)
　　{
　　int n=sc.nextInt ();
　　int []=new int [n];
　　for (int j=0;j & lt;n;j + +)
　　{
　　一个[j]=sc.nextInt ();
　　}
　　Arrays.sort(一个);
　　f (A);
　　System.out.println(时间);
　　时间=0 l;
　　}
　　}
　　公共静态孔隙f (int []) {
　　如果(一个。长度==3){
　　时间+=[0]+ [1]+ [2];
　　返回;
　　}
　　如果(一个。长度==2){
　　时间+=[1];
　　返回;
　　}
　　如果(一个。长度==1){
　　时间+=[0];
　　返回;
　　}
　　如果([0]+ [。长度- 2]& lt;[1]* 2){
　　时间+=2 * [0]+ [。——2]+[长度。长度- 1];
　　其他}{
　　时间+=[0]+ 2 * [1]+ [。长度- 1];
　　}
　　int [] B=数组。copyOfRange (0。长度- 2);
　　f (B);
　　}
　　}