#include #include #include #define INFINITY 1000000000 int **gencosts ( int n ) { int **C, i, j; printf("\n+++ Flyover building costs\n"); C = (int **)malloc((n-1)*sizeof(int *)); for (i=0; i<=n-2; ++i) { printf(" "); C[i] = (int *)malloc(n * sizeof(int)); for (j=0; j<=n-1; ++j) { C[i][j] = 5 + rand() % 16; printf(" %2d", C[i][j]); } printf("\n"); } return C; } int greedy ( int **C, int n ) { int TC, i, j, k, h, kmin, TCnew, TCmin; TC = 0; i = j = h = 0; while (i < n-1) { kmin = j; TCmin = TC + C[i][j]; for (k=j+1; k<=n-1; ++k) { if (i) TC += 5; TCnew = TC + C[i][k]; if (TCnew < TCmin) { kmin = k; TCmin = TCnew; } } if (i) h += (kmin - j); ++i; j = kmin; TC = TCmin; printf(" Building flyover from (%d,%d) to (%d,%d): Cost = %2d\n", i-1, j, i, j, C[i-1][j]); } printf(" Total cost of the horizontal segments = %2d\n", 5*h); return TC; } int DP ( int **C, int n ) { int **T; int i, j; int TC, TC1, TC2; T = (int **)malloc(n * sizeof(int *)); for (i=0; i<=n-1; ++i) { T[i] = (int *)malloc(n * sizeof(int)); if (i == 0) { for (j=0; j<=n-1; ++j) T[i][j] = 0; } else { for (j=0; j<=n-1; ++j) { TC1 = (j == 0) ? INFINITY : T[i][j-1] + 5; TC2 = T[i-1][j] + C[i-1][j]; T[i][j] = (TC1 <= TC2) ? TC1 : TC2; } } } TC = T[n-1][0]; for (j=1; j<=n-1; ++j) { if (T[n-1][j] < TC) TC = T[n-1][j]; } for (i=0; i<=n-1; ++i) free(T[i]); free(T); return TC; } void DPsol ( int **C, int n ) { int **T; char **D; int *S; int i, j, k; int TC, TC1, TC2; T = (int **)malloc(n * sizeof(int *)); D = (char **)malloc(n * sizeof(char *)); for (i=0; i<=n-1; ++i) { T[i] = (int *)malloc(n * sizeof(int)); D[i] = (char *)malloc(n * sizeof(char)); if (i == 0) { for (j=0; j<=n-1; ++j) { T[i][j] = 0; D[i][j] = 'S'; } } else { for (j=0; j<=n-1; ++j) { TC1 = (j == 0) ? INFINITY : T[i][j-1] + 5; TC2 = T[i-1][j] + C[i-1][j]; if (TC1 <= TC2) { T[i][j] = TC1; D[i][j] = 'H'; } else { T[i][j] = TC2; D[i][j] = 'V'; } } } } TC = T[n-1][0]; j = 0; for (i=1; i<=n-1; ++i) { if (T[n-1][i] < TC) { TC = T[n-1][i]; j = i; } } S = (int *)malloc((n-1)*sizeof(int)); i = n-1; k = 0; while (i > 0) { if (D[i][j] == 'H') { ++k; --j; } else { --i; S[i] = j; } } for (i=0; i<=n-2; ++i) { printf(" Building flyover from (%d,%d) to (%d,%d): Cost = %2d\n", i, S[i], i+1, S[i], C[i][S[i]]); } printf(" Total cost of the horizontal segments = %2d\n", 5*k); for (i=0; i<=n-1; ++i) { free(T[i]); free(D[i]); } free(T); free(D); free(S); } int main ( int argc, char *argv[] ) { int n; int **C, TC; if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n); printf("n = %d\n", n); srand((unsigned int)time(NULL)); C = gencosts(n); printf("\n+++ Part 1: Greedy algorithm\n"); TC = greedy(C,n); printf("--- Total cost = %d\n", TC); printf("\n+++ Part 2: Dynamic programming algorithm\n"); TC = DP(C,n); printf("--- Total cost = %d\n", TC); printf("\n+++ Part 3: Dynamic programming algorithm with solution\n"); DPsol(C,n); exit(0); }