4.1 题目描述

牛童骑在牛背上过河，共有甲、乙、丙、丁四头牛，甲牛过河要2分钟，乙牛过河要3分钟，丙牛过河要8分钟，丁牛过河要5分钟，每次只能赶两头牛过河。问：要把四头牛都赶到河对岸去，最少要多少分钟。（提示：牛童回来赶牛过河也得骑在牛背上）。

4.2 程序使用说明

  1. 输入牛的头数n；
    2. 输入每头牛的耗时spend。

    4.3 分析和设计

  2. 思路
    当只有一头牛时，直接赶过去。当有两头及以上未过河时，一次就需要赶两头牛，如果还有牛未赶过来就需要把一头牛赶回去。以此类推，只要有牛未过河就需要继续赶，在这里运用深度遍历的方法，当所有牛都过河后就等到一个可行解，由于赶牛时有不同的选取方式，这就产生了多个可行解，需要遍历所有解才能找到最优解。
    2. 伪代码
    1. CrossRiver(left[0...n], right[0...m])
    2. // 输入：未过河的牛left，已过河的牛right
    3. // 输出：过河最少时间
    4. minTime <- sum(left)
    5. if n = 1
    6.  // 只有一头牛
    7.  Return left[0]
    8. for i <- 1 to n do
    9.  for j <- i+1 to n do
    10.      // 选两头牛过河
    11.      nowTime <- 0
    12.      // 不能在原位上修改
    13.      newLeft <- left
    14.      NewLeft.remove(j)
    15.      newLeft.remove(i)
    16.      newRight <- right
    17.      newRight.add(left[i])
    18.      newRight.add(left[j])
    19.      nowTime <- nowTime+max(left[i], left[j])
    20.      if newLeft.length > 0
    21.          // 左边还有牛未过河，牧童要回到右边
    22.          for k <- 1 to newRight.length-1 do
    23.              tempLeft <- newLeft
    24.              tempLeft.add(newRight[k])
    25.              tempRight <- newRight
    26.              tempRight.remove(k)
    27.              tempTime <- nowTime+newRight[k]
    28.              // 当前时间加上把剩余的牛驱赶过去的时间就是总时间
    29.              tempTime <- tempTime + CrossRiver(tempLeft, tempRight)
    30.              if tempTime < minTime
    31.                  minTime <- tempTime
    32.      else if nowTime < minTime
    33.          minTime <- nowTime
    34. return minTime
  3. 时间复杂度
    当有n头牛时，从左边任选两头牛最多有n(n-1)/2种方案，即(n-1)+(n-2)+…+1，而从右边选一头牛回来最多有n-1种方案，而整个过程需要n-1个来回，所以时间复杂度为{[n(n-1)/2]*(n-1)}n-1∈O(n3n)

    4.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | n = 4
    spend = [2, 3, 8, 5] | 19 | 19 | 通过 | | 2 | n = 5
    spend = [3, 5, 8, 7, 6] | 35 | 35 | 通过 | | 3 | N = 2
    Spend = [2, 3] | 3 | 3 | 通过 |

4.5 源代码（含注释）

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. import java.util.Scanner;
  5. public class CrossRiver {
  6.     int[] spend = new int[]{2, 3, 8, 5};
  7.     int minTime = Integer.MAX_VALUE;
  8.     public static void main(String[] args) {
  9.         System.out.println("请输入牛头数：");
  10.         Scanner scanner = new Scanner(System.in);
  11.         int n = scanner.nextInt();
  12.         System.out.println("请输入"+n+"头牛耗时：");
  13.         int[] spend = new int[n];
  14.         for (int i = 0; i < n; i++){
  15.             spend[i] = scanner.nextInt();
  16.         }
  17.         CrossRiver crossRiver = new CrossRiver(spend);
  18.         crossRiver.crossing();
  19.         System.out.println("贪心算法结果："+ crossRiver.minTime);
  20.         crossRiver.minTime = Integer.MAX_VALUE;
  21.         List<Integer> list = new ArrayList<>();
  22.         for (int i = 0; i < crossRiver.spend.length; i++) {
  23.             list.add(crossRiver.spend[i]);
  24.         }
  25.         crossRiver.minTime = crossRiver.crossing(list, new ArrayList<>());
  26.         System.out.println("遍历算法结果："+crossRiver.minTime);
  27.     }
  28.     public CrossRiver(int[] spend) {
  29.         this.spend = spend;
  30.     }
  31.     public CrossRiver() {
  32.     }
  33.     /**
  34.      * 在1、2、3头牛时，驱赶方式是固定的
  35.      * 在剩余牛大于等于4时，运用贪心算法的思想，借助最快的把最慢的先赶过去，为此需要先对耗时排序
  36.      * 有两种方案能较快驱赶最慢的两头牛：
  37.      * 1. 最快的(即所用时间spend[0])和次快的过河,然后把最快的赶回来,再次慢的和最慢的过河,然后把次快的赶回来.
  38.      * 即所需时间为:spend[1]+spend[0]+spend[n-1]+spend[1] = spend[0]+2*spend[1]+spend[n-1]
  39.      * 2. 最快的和最慢的过河,然后把最快的赶回来,再最快的和次慢的过河,然后把最快的赶回来.
  40.      * 即所需时间为:spend[n-1]+spend[0]+spend[n-2]+spend[0] = 2*spend[0]+spend[n-2]+spend[n-1]
  41.      */
  42.     public void crossing() {
  43.         // 对花费时间进行排序
  44.         Arrays.sort(this.spend);
  45.         int left = this.spend.length;
  46.         int sum = 0;
  47.         while (left > 0) {
  48.             if (left == 1) {
  49.                 sum += spend[0];
  50.                 break;
  51.             } else if (left == 2) {
  52.                 sum += spend[1];
  53.                 break;
  54.             } else if (left == 3) {
  55.                 // 先把最慢的赶过去，然后用最快的回来，再把剩余的赶过去
  56.                 sum += spend[2] + spend[0] + spend[1];
  57.                 break;
  58.             } else {
  59.                 sum += Math.min(spend[0] + 2 * spend[1] + spend[left - 1], 2 * spend[0] + spend[left - 2] + spend[left - 1]);
  60.                 left -= 2;
  61.             }
  62.         }
  63.         minTime = sum;
  64.     }
  65.     /**
  66.      * 深度遍历，先从左边选两个赶到右边，再从右边选一个赶到左边，然后再递归调用，直到左边没有牛
  67.      * @param left 左边牛状态
  68.      * @param right 右边牛状态
  69.      */
  70.     public int crossing(List<Integer> left, List<Integer> right) {
  71.         int minTime = Integer.MAX_VALUE;
  72.         if (left.size() == 1){
  73.             return left.get(0);
  74.         }
  75.         for (int i = 0; i < left.size(); i++) {
  76.             for (int j = i + 1; j < left.size(); j++) {
  77.                 int nowTime = 0;
  78.                 // 两两组合从左到右，选择两个移动到右边
  79.                 List<Integer> newLeft = new ArrayList<>(left);
  80.                 newLeft.remove(j);
  81.                 newLeft.remove(i);
  82.                 List<Integer> newRight = new ArrayList<>(right);
  83.                 newRight.add(left.get(i));
  84.                 newRight.add(left.get(j));
  85.                 nowTime += Math.max(left.get(i), left.get(j));
  86.                 if (newLeft.size() > 0) {
  87.                     // 左边有剩余，需要牛童回到左边
  88.                     for (int k = 0; k < newRight.size(); k++) {
  89.                         List<Integer> tempLeft = new ArrayList<>(newLeft);
  90.                         tempLeft.add(newRight.get(k));
  91.                         List<Integer> tempRight = new ArrayList<>(newRight);
  92.                         tempRight.remove(k);
  93.                         int tempNowTime = nowTime+newRight.get(k);
  94.                         // 在当前状态继续驱赶剩余的牛
  95.                         tempNowTime+=crossing(tempLeft, tempRight);
  96.                         if (tempNowTime < minTime){
  97.                             minTime = tempNowTime;
  98.                         }
  99.                     }
  100.                 } else if (nowTime < minTime) {
  101.                     minTime = nowTime;
  102.                 }
  103.             }
  104.         }
  105.         return minTime;
  106.     }
  107. }