小飞的电梯调度算法

1. 问题描述：

亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：

由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。

问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？

2. 【解法一】暴力求解（枚举法）时间复杂度O(N²)

1 package chapter1youxizhileElevatorScheduling; 2 /** 3  * 小飞的电梯调度算法 4  * 【解法一】枚举法 5  * @author DELL 6  * 7  */ 8 public class ElevatorScheduling1 { 9     private int nPerson[];  //nPerson[i]表示到第i层的乘客数目10     private int nFloor;  //电梯的总层数11     //构造函数12     public ElevatorScheduling1(int[] nPerson, int nFloor){13         this.nPerson = nPerson;14         this.nFloor = nFloor;15     }16     17     public int getTargetFloor(){18         int minFloor = 30*nFloor; //记录爬楼梯总和的最小值，初始时设为一个较大的值19         int targetFloor = -1;  //电梯停的目标层，初始为-120         for(int i=1;i<=nFloor;i++){  //逐个试探i值21             int sum = 0;  //记录爬楼梯的总数和22             for(int j=0;j
     
      sum){26                 minFloor = sum;27                 targetFloor = i;28             }29         }30         System.out.println("爬楼梯层数的最小值为："+minFloor);31         return targetFloor;32     }33     public static void main(String[] args) {34         int nPerson[] = {0,1,3,3,4,6,8,4};35         ElevatorScheduling1 es = new ElevatorScheduling1(nPerson, 8);36         System.out.println("电梯的目标层应为："+es.getTargetFloor());37 38     }39 40 }
     

 

程序运行结果如下：

爬楼梯层数的最小值为：39电梯的目标层应为：6

 

3.【解法二】动态规划（时间复杂度为O(N)）

1 package chapter1youxizhileElevatorScheduling; 2 /** 3  * 小飞的电梯调度算法 4  * 【解法二】动态规划 5  * @author DELL 6  * 7  */ 8 public class ElevatorScheduling2 { 9     private int nPerson[];  //nPerson[i]表示到第i层的乘客数目10     private int nFloor;  //电梯的总层数11     //构造函数12     public ElevatorScheduling2(int[] nPerson, int nFloor){13         this.nPerson = nPerson;14         this.nFloor = nFloor;15     }16     17     /**18      * 计算目标层19      * @return 目标层20      */21     public int getTargetFloor(){22         int minFloor = 0; //记录爬楼梯总和的最小值23         int targetFloor = -1;  //电梯停的目标层，初始为-124         int i;25         int N1; //第i层以下的乘客数目26         int N2; //第i层的乘客数目27         int N3; //第i层以上的乘客数目28         //计算第一层的N1,N2,N3值29         N1 = 0;30         N2 = nPerson[0];31         for(N3=0,i=1;i

程序运行结果如下：

爬楼梯层数的最小值为：39电梯的目标层应为：6

 扩展问题：

　　往上爬楼梯，总是比往下走要累的。假设往上爬一个楼层，要耗费k单位的能量，而往下走只需要耗费1单位的能量，那么如果题目条件改为让所有人消耗的能量最少，这个问题怎么解决呢？

　【解法一】暴力求解（枚举法）时间复杂度O(N²)

只需将上述【解法一】中的

22             for(int j=0;j

改为：

int j;            for(j=0;j

  【解法二】动态规划（时间复杂度为O(N)）

只需将上述【解法二】中的

31         for(N3=0,i=1;i

改为：

for(N3=0,i=1;i