代码写得有点长,你自己优化一下,希望可以帮到你
- import java.util.ArrayList;
- /**
- * 思路:在桥这边枚举两个人过去,然后在桥那表让花时最小的送手电筒回来,
- * 然后继续枚举两个人过桥,再让花时最小的送手电筒回来,循环的,直到这边的人只剩下两个。
- */
- class Tie_2
- {
- // 记录过程
- private static String changes = "";
- // 标记是否成功过桥,若成功过了,那么就跳出,不找了
- private static boolean isCross = false;
- public static void main(String[] args)
- {
- ArrayList<Integer> here = new ArrayList<Integer>();
- ArrayList<Integer> there = new ArrayList<Integer>();
- init(here,there);
- // 枚举两个人过桥
- o:for(int i=0; i<here.size(); i++)
- {
- for(int j=0; j<here.size(); j++)
- {
- if(i==j)
- continue;
- int timeone = here.get(i);
- int timetwo = here.get(j);
- if(!isCross){
- crossBridge(here,there,timeone,timetwo,0);
- init(here,there);
- }else{
- break o;
- }
- }
- }
- }
- // 初始化数据
- public static void init(ArrayList<Integer> here,ArrayList<Integer> there)
- {
- here.clear();
- there.clear();
- here.add(1);
- here.add(2);
- here.add(5);
- here.add(10);
- }
- // 过桥
- public static void crossBridge(ArrayList<Integer> a, ArrayList<Integer> b, int timeone, int timetwo,int allTime)
- {
- // 取出花时最大的
- int bigTime = timeone > timetwo ? timeone : timetwo;
- changes += "这边:" + a +" -------桥-------- " + "那边:"+b + "\n\t" +timeone + "和" + timetwo + "一起过桥!---用时:"+bigTime+"分\n";
- // 将过桥的两个存在b集合,代表过桥了
- b.add(timeone);
- b.add(timetwo);
- allTime += bigTime; // 一共用了多少时间
- // 把过桥的两个人在a集合中删除
- for(int i=0;i<a.size();i++)
- if(timeone==a.get(i)){
- a.remove(i);
- break;
- }
- for(int i=0;i<a.size();i++)
- if(timetwo==a.get(i)){
- a.remove(i);
- break;
- }
-
- // 在这边找一个花时最小的送手电筒回去
- int smallTimeIndex = getSmallTime(b); // 花时最小的时间的角标
- changes += "这边:" + a +" -------桥-------- " + "那边:"+b+"\n\t"
- + b.get(smallTimeIndex) + "送手电筒回去!---用时:" +b.get(smallTimeIndex)+"分\n";
- allTime += b.get(smallTimeIndex); // 累加时间
- a.add(b.get(smallTimeIndex)); // 送手电筒回去了,就添加到a集合
- b.remove(smallTimeIndex);
- // 出口判断
- if(a.size()==2 && b.size()==2)
- {
- bigTime = Math.max(a.get(0),a.get(1));
- allTime+=bigTime;
- if(allTime > 17)
- {
- changes = "";
- return;
- }
- System.out.println(changes +"\t"+ a.get(0)+"和"+a.get(1) +"一起过桥!---用时:"+bigTime+"分");
- System.out.println("\t一共花时:"+allTime+"分");
- isCross = true; // 标记已经成功过桥了
- changes = "";
- return;
- }
- // 继续枚举两个人过桥
- for(int i=0; i<a.size(); i++)
- {
- for(int j=0; j<a.size(); j++)
- {
- if(i==j)
- continue;
- timeone = a.get(i);
- timetwo = a.get(j);
- if((allTime + (timeone > timetwo ? timeone : timetwo)) > 17)
- continue;
- crossBridge(a,b,timeone,timetwo,allTime);
- }
- }
-
- }
- // 获取b集合中花时最小时间的角标
- public static int getSmallTime(ArrayList<Integer> b)
- {
- int small = Integer.MAX_VALUE;
- int index = -1;
- for(int i=0;i<b.size();i++)
- if(small > b.get(i))
- {
- small = b.get(i);
- index = i;
- }
- return index;
- }
- }
复制代码
输出结果:
这边:[1, 2, 5, 10] -------桥-------- 那边:[]
1和2一起过桥!---用时:2分
这边:[5, 10] -------桥-------- 那边:[1, 2]
1送手电筒回去!---用时:1分
这边:[5, 10, 1] -------桥-------- 那边:[2]
5和10一起过桥!---用时:10分
这边:[1] -------桥-------- 那边:[2, 5, 10]
2送手电筒回去!---用时:2分
1和2一起过桥!---用时:2分
一共花时:17分 |