《编程之美》中“小飞的电梯调度算法”停k层的解法

#include <iostream>#include <time.h>#include <cassert>using namespace std;const int totalFloorNum = 10;const int totalStopNum = 4;int nPerson[totalFloorNum + 1];int minFloors[totalFloorNum + 1][totalStopNum + 1];int targetFloors[totalFloorNum + 1][totalStopNum + 1];//stopNum floors between (totalFloorNum - floor + 1)th floor and (totalFloorNum)th floor//the last stop is totalFloorNum - floorint compute(int floor, int stopNum){if(minFloors[floor][stopNum] >= 0)return minFloors[floor][stopNum];//determine the first stop in the remaining (floor) floorsint min = totalFloorNum - floor + 1;int max = totalFloorNum + 1 - stopNum;assert(min <= max);//the next possible step can range from min to maxint minFloor = -1;int targetFloor = -1;if(stopNum == 1){//if only need to stop once, just copy the code from Beauty of Programmingint n1 = 0;int n2 = nPerson[min];int n3 = 0;minFloor = 0;targetFloor = min;for(int i = min + 1; i <= totalFloorNum; i++){n3 += nPerson[i];minFloor += nPerson[i] * (i - min);}for(int i = min + 1; i <= totalFloorNum; i++){if(n1 + n2 < n3){targetFloor = i;minFloor += (n1 + n2 - n3);n1 += n2;n2 = nPerson[i];n3 -= n2;}elsebreak;}}else{for(int i = min; i <= max; i++){int mid = (min - 1 + i) / 2;int temp = 0;if(min == 1){for(int j = 1; j < i; j++){temp += (i - j) * nPerson[j];}}else{//passengers who want to go to from (min - 1) to mid will get off at (min - 1)th floorfor(int j = min; j <= mid; j++){temp += (j - min + 1) * nPerson[j];}//passengers who want to go to from (mid + 1) to (i) will get off at (i)th floorfor(int j = mid + 1; j < i; j++){temp += (i - j) * nPerson[j];}}temp += compute(totalFloorNum - i, stopNum - 1);if(temp < minFloor || minFloor == -1){minFloor = temp;targetFloor = i;}}}minFloors[floor][stopNum] = minFloor;targetFloors[floor][stopNum] = targetFloor;return minFloor;}int main(){memset(nPerson, 0, (totalFloorNum + 1) * sizeof(int));srand(time(NULL));for(int i = 1; i <= totalFloorNum; i++){nPerson[i] = rand() % 100;}for(int i = 1; i <= totalFloorNum; i++){for(int j = 1; j <= totalStopNum; j++){minFloors[i][j] = -1;}}for(int i = 1; i <= totalFloorNum; i++){cout <<i <<"th floor: " <<nPerson[i] <<" persons" <<endl;}int minFloor = compute(totalFloorNum, totalStopNum);cout <<"The floors selected is: " <<endl;int floor = totalFloorNum;int stopNum = totalStopNum;while(stopNum >= 1){int selectedFloor = targetFloors[floor][stopNum];cout <<"The " <<(totalStopNum - stopNum + 1) <<"th selected floor is: "<<selectedFloor <<endl;floor = totalFloorNum - selectedFloor;stopNum--;}cout <<"Min floors: " <<minFloor <<endl;system("pause");}