小飞的电梯调度算法 - 编程之美1.8

小飞的电梯调度算法  - 编程之美1.8
亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：
由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。

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

对于一个给定的有序数组 {1,3,5,5,7,9}, 求一个数，使得数组中每个数和这个数的差的绝对值的总和最小。
http://www.cppblog.com/jake1036/archive/2011/06/29/149720.html
(1)使用简单的方法，直接将楼层从1到n开始遍历
sum(person[i] * |i - j| ) 此表达式为一个双重循环，i与j均为1-n的循环。
j下标表示电梯停靠的楼层。
person数组表示，对应i层的下电梯的人数。此算法负责度为o(n*n)
对应的j是上述和为最小的一层即为所求。 上面的算法复杂度为o(n)

(2)下面考虑一个简单的算法，使其复杂度达到o(n)
考虑假如电梯停靠在某一楼层i处，假设在i处下楼的客人为N2,
在i以上楼层的客人数目为N3 ，在i一下楼层的客人数目为N1。
且将电梯在i层停止时，全部人员的路程之和记为T。

那么加入电梯在i-1层停的话，则原来i层之上的人需要多爬一层，即增加了N3
第i层的人需要多爬一层，则结果增加了N2, i层之下的人则少爬了一层，结果减去N1
所以第i-1层的结果为 T - N1 + N2 + N3 。即结果可以即为 T -(N1 - N2 - N3)

下面考虑在i+1层的结果，若电梯在i+1层停止的话，原来i层之上的客户都会少爬一层，
则结果减少N3 ，而i层之下的人员则都会多爬一层即增加了N1 ，第i层的人员都会多爬一层
即为增加了N2 。则结果为 T + N1 + N2 - N3

综上我们得出，
(1)若N1 > N2 + N3的时候， 我们在第i-1层 选择电梯停止最好。
(2)若N1 + N2 < N3的时候， 我们选择在第i+1层停止电梯最好。

下面我们可以先计算出来当i=1时候的T ，然后判断是否需要在i+1层停止，若是i+1层的花费
大于i层，则我们可以继续计算，否则退出。const int N = 10 ;
 int person[N+1] = {0 , 2 , 5 , 7 , 3 , 5 , 2 , 6, 2 , 6 , 3} ;

  int floor2()
  {
      //先计算出在第一层停止的时候 所需要的花费
       int T = 0;
       int N1 = 0 ; //在第一层以下下的人数 
       int N2 = person[1] ; //在第一层处下的人数 
       int N3 = 0 ;      //在第一层之上下电梯的人数 
       int floor =  1 ;
       for(int i = 2 ; i <= N ;i++) //先计算出第1层停止需要爬取的楼层数目 
       {
         T += person[i] * (i - 1) ;
         N3 += person[i] ;  
       
       }
       for(int i = 2 ; i <= N ;i++)
       {
         if(N1 + N2 <= N3) //说明第i+1层的结果会大于第i层 
           {
               T += N1 + N2 - N3 ;
               N1 += N2 ;
               N2 = person[i] ;
               N3 -= person[i] ;
               floor = i ;
            
           }  
           else  //否则第i层的结果已经最小，故不需要计算第i+1层 
           break ;
         
       }  
       return floor ;
  }
  int floor1() //使用简单算法计算 
  {
      int tempfloor = 0 ;
      int min = 6553 ;//存储最小值
      int floor = 1   ;//存储停靠的楼层 
      int i , j ;
   
      for( i = 1 ; i <= N ;i++) //表示第i楼层电梯停靠 
      {
        tempfloor = 0 ;
                    
        for( j = 1 ; j < i ;j++)   
            tempfloor += (i - j) * person[j] ;    
                      
        for(j = i + 1 ; j <= N ; j++)      
            tempfloor += (j - i) * person[j] ; 
     
        if(min > tempfloor)
        {
          min = tempfloor ;
          floor = i ;       
        }    
     //   cout<<"tempfloor"<<i<<":"<<tempfloor<<endl;                   
      }
      return floor ;
  }

http://blog.csdn.net/lonelycatcher/article/details/7910877
方法二：书上提供的O(N)的动态规划的算法。

假设电梯停在i层楼，可以计算出所有乘客要爬楼层的层数为Y,假设此时有N1个乘客在i层楼以下，N2个乘客在I层楼，N3个乘客在I层楼以上，则当电梯停在i+1层的时候，N1+N2个乘客要多下一层楼，共多下N1+N2层，N3个乘客要少往上面爬一层楼，少上N3层楼，此时Y(i+1) = Y(i) + N1+N2-N3，很显然，当N1+N2<N3的时候，Y不断减小。Y1很容易算出来，另外我们还可以看出，N1+N2是递增的，N3是递减的，所以N1+N2一旦大于N3的时候，我们直接退出循环即可，没有必要再计算下去了。
http://bylijinnan.iteye.com/blog/1564976

1.     public void opt(int[] person){  
2.         if(person==null){  
3.             return;  
4.         }  
5.         if(person.length<2){//如果没有人到二楼或者更高，那就不用坐电梯了  
6.             return;  
7.         }  
8.         int N=person.length-1;  
9.         targetFloor=2;//先让电梯停在二楼，计算N1,N2  
10.         int N1=0;  
11.         int N2=person[2];  
12.         int N3=0;  
13.         //电梯停在二楼，计算N3以及总楼梯数MinFloor  
14.         for(int j=3;j<=N;j++){  
15.             N3+=person[j];  
16.             minStairs+=person[j]*(j-targetFloor);  
17.         }  
18.         //让电梯依次改停在3楼、4楼...N楼,出现更优解时,则调整电梯停靠层数以及N1,N2,N3  
19.         for(int i=3;i<=N;i++){  
20.             if(N1+N2<N3){  
21.                 targetFloor=i;  
22.                 N1=N1+N2;  
23.                 N2=person[i];  
24.                 N3=N3-person[i];  
25.                 minStairs+=N1+N2-N3;  
26.             }  else break; // missing...
27.         }  
28.     }

方法三：中位数
http://www.cnblogs.com/moqiguzhu/p/3837942.html

假设乘客数是n，想去的对应楼层是N1,N2,...,Nn。要求N，使得min{∑i|N-Ni|}

如果我们能对序列N1,N2,...,Nn排序，得到一个有序序列为Nk1,Nk2,...,Nkn。那么问题可以表述为：求N，使得min{∑i|N-Nki|} (Nk1<=Nk2<=...<=Nkn)。

把上面的式子看成是一个关于N的函数，我们很容易想象出这个函数的曲线——大概就是一个端口朝上的二元一次函数的曲线。

下面的问题就是怎么找到取极小值的N，其实想象出函数的曲线，这个问题也是非常直接的。

如果n是奇数，当N是中位数的时候，能取到极小值。

如果n是偶数，N取有序序列最中间的两个数或者这两个数之间任何一个数都能取到极小值。比如说，序列是2,3,5,7，那么N=3,4或者5都是极小值。

以上的两个结论证明起来也非常简单，这里不再赘述，有兴趣的同学不妨在纸上画一画。

http://blog.csdn.net/lonelycatcher/article/details/7910877

其实这道题目仔细分析起来就是求一组数据的中位数而已。假设两人，分别到3层楼和8层楼下，在3和8之间取一点，使得到两个点距离最小，很显然，在3和8中的每一点到3和8的距离之和都是相等的。推广到2 3 5 5 6 7 8 8 9这样一组数据，target_floor为中位数。

扩展N个人，电梯只要停在中位数花费不会变，否则会增加。故只需求出中位数即可，如果N是偶数，停在中间那两个数任何一个都OK。

1. int nPerson[N+1];  
2. int target_floor;  
3.   
4. int left = 1,right = N;  
5. while(right-left > 1)  
6. {  
7.     while(nPerson[left] == 0)left++;  
8.     nPerson[left] --;  
9.     while(nPerson[right] == 0)right--;  
10.     nPerson[right] --;  
11. }  
12. return left;  

扩展问题1的解法
如果往上爬楼梯比较累，往下走较容易，假设往上走一层耗费k单位的能量，往下走一层只耗费1单位的能量。
解法二更加适合。只需要计算N1+N2-N3变成N1+N2-N3*K即可。其余的都是一样的。
http://www.xuebuyuan.com/1811421.html
则改为i+1层停之后原先i层以上的乘客即N3个乘客少往上爬一层，原先第i层的N2个乘客需多往下爬一层，原先第i层以下的N1个乘客需多往下爬一层。

所需总能量变为E-N3*K+N1+N2

若N3*K>(N1+N2)，则停在i+1层好

若停第i层比停i+1层能量消耗低，会出现停第i层比停第i+2层能量消耗多的情况么

已知 N3*K<(N1+N2)

从i层到i+2层

消耗的能量变为E+2(N1+N2)+nPersons[i+1]-k(N3-nPersons[i+1])>E

因此循环只要有一次停第i层比停i+1层能量消耗低，后面变无需再比较。

53	int GetTargetFloor3(int* nPerson,int n,double& nMinEnergy,int k){//书中扩展1的代码

54	nMinEnergy = 0;

55	int nTargetFloor = 1;

56	int N1,N2,N3;

57

N1 = 0;

58	N2 = nPerson[1];

59

N3 = 0;

60	for(int i=2;i<=n;i++){

61	N3 += nPerson[i];

62	nMinEnergy +=k*nPerson[i]*(i-1);

63

}

64	cout<<"第1层停靠耗费总能量:"<<nMinEnergy<<endl;

65	for(int i=2;i<=n;i++){

66	if(N1+N2<N3*k){

67	nMinEnergy +=N1+N2-N3*k;

68	nTargetFloor =i;

69	cout<<"第"<<i<<"层停靠耗费总能量:"<<nMinEnergy<<endl;

70

N1 += N2;

71	N2  = nPerson[i];

72	N3 -= nPerson[i];

73

}else

74

break;

75

}

76	return nTargetFloor;

77

}

http://blog.163.com/guixl_001/blog/static/41764104201082062317857/
有一栋楼，一共有N层，要去每一层的人分别是A[1],A[2]....A[N]，如果电梯可以停K次，问停在哪K层让所有人走的矩离最短？

用一个数组opt[i][j]记录电梯前i次停在1到j层之间，所有人走的路的最短矩离。用cost[i][j]记录如果电梯从第i层到第j层只能停一次，电梯停在最佳位置让所有人走的矩离最短的最优解。那么cost[i][j]怎么求呢？（这里把这个解法省略，具体可参见编程之美“小飞的电梯调度”）。如果前i次停留在前j层，那么第i+1次停留在第j+1至j+k层(j+k<=n)，则状态转移方程为
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)

Cost数组存放电梯从第i层到j层停一次的最小走动矩离，构造cost的代码如下：

for(i=1;i<=m;i++)
for(j=i;j<=m;j++)
{
    cost[i][j] = 0;
    mid = 求得电梯在i到j层的最佳停留位置;
   for(k=i;k<=j;k++)
        cost[i][j]+=(distance[mid]-distance[k])>=0 ?distance[mid]-distance[k]:distance[k]-distance[mid];
}
Opt[i][j] 表示从电梯在第1层到第j层停i次所有人的最小走动矩离，对于i=1（即电梯只停一次的情况）来说，opt[i][j] = cost[i][j],如果让电梯在1 至 j层停两次，也就是i=2的情况，可能是下面一种情况的最优解：
第一次停在第一层，第二次停在2至j层；
第一次停在1至2层，第二次停在3至j层；
第一次停在1至3层，第二次停在4至j层；
等等。。。。。
该部分的代码如下：

for(i=0;i<=n;i++)

        for(j=0;j<=m;j++)

            if(opt[i][j]<Integer.max)

            {

                for(k=1;j+k<=m;k++)

                {

                    if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k])

                    {

                        opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k];

                    }

                }

            }