jake1036

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

  编程之美-电梯调度算法

  一问题描述:
     所有的员工均在1楼进电梯的时候,选择所要到达的楼层。
     然后计算出停靠的楼层i,当到达楼层i的时候,电梯停止。
     所有人走出电梯,步行到所在的楼层中。
     求所有人爬的楼层数目和的最小值。 
 
二 问题解决方法:
    二 解决方案:
  (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层,则我们可以继续计算,否则退出。
  三 代码如下:
     

#include <iostream>
  
using namespace std ;
 
 
const int N = 10 ;
 
int person[N+1= {0 , 2 , 5 , 7 , 3 , 5 , 2 , 62 , 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 ;
  }

  
  
  
int main()
  
{      
    
int temp1 = floor1() ;  
    
int temp2 = floor2() ;  
    cout
<<temp1<<" "<<temp2<<endl ;
    getchar() ;
    
return 0 ;    
  }

    


            

posted on 2011-06-29 11:03 kahn 阅读(4124) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理