/* elevator.c Elevator stop optimization via dynamic programming. */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #define NFLOORS 25 /* the height of the building in floors */ #define MAX_RIDERS 50 /* what is the capacity of the elevator? */ #define MAXINT 100007 int stops[MAX_RIDERS]; /* what floor does everyone get off at? */ int nriders; /* number of riders */ int nstops; /* number of allowable stops */ int m[NFLOORS+1][MAX_RIDERS]; /* dynamic programming cost table */ int p[NFLOORS+1][MAX_RIDERS]; /* dynamic programming parent table */ int min(int a, int b) { if (a < b) { return(a); } return(b); } int floors_walked(int previous, int current) { int nsteps=0; /* total distance traveled */ int i; /* counter */ for (i = 1; i <= nriders; i++) { if ((stops[i] > previous) && (stops[i] <= current)) { nsteps += min(stops[i]-previous, current-stops[i]); } } return(nsteps); } /* m[i][j] denotes the cost of serving all the riders using j stops, the last of which is at floor i. Zero is the originating floor. */ int optimize_floors() { int i, j, k; /* counters */ int cost; /* costs placeholder */ int laststop; /* the elevator's last stop */ for (i = 0; i <= NFLOORS; i++) { m[i][0] = floors_walked(0, MAXINT); p[i][0] = -1; } for (j = 1; j <= nstops; j++) { for (i = 0; i <= NFLOORS; i++) { m[i][j] = MAXINT; for (k = 0; k <= i; k++) { cost = m[k][j-1] - floors_walked(k, MAXINT) + floors_walked(k, i) + floors_walked(i, MAXINT); if (cost < m[i][j]) { m[i][j] = cost; p[i][j] = k; } } } } laststop = 0; for (i = 1; i <= NFLOORS; i++) { if (m[i][nstops] < m[laststop][nstops]) { laststop = i; } } return(laststop); } void reconstruct_path(int lastfloor, int stops_to_go) { if (stops_to_go > 1) { reconstruct_path(p[lastfloor][stops_to_go], stops_to_go-1); } printf("%d\n", lastfloor); } void print_matrix(int m[NFLOORS+1][MAX_RIDERS]) { int i, j; /* counters */ for (j = 0; j <= nstops; j++) { for (i = 0; i <= NFLOORS; i++) { printf("%3d", m[i][j]); } printf("\n"); } } int main(void) { int i; /* counter */ int laststop; scanf("%d %d", &nriders, &nstops); for (i = 1; i <= nriders; i++) { scanf("%d", &(stops[i])); } for (i = 1; i <= nriders; i++) { printf("%d\n", stops[i]); } laststop = optimize_floors(); print_matrix(m); printf("\n"); print_matrix(p); printf("cost = %d\n", m[laststop][nstops]); reconstruct_path(laststop, nstops); return 0; }