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層只能停一次，電梯停在最佳位置讓所有人在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];

????????????????????}

????????????????}

????????????}

總結

以上是生活随笔為你收集整理的编程之美---小飞的电梯调度问题 1.8 扩展2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。