1. Optimizing the gaps
Consider the following optimization problem. You are a developer. There are n lots on a street, and for each lot there is a reward (which may be negative) for building a house on that lot. However, the town has strict rules on how big or small the gap between two houses (expressed in terms of empty lots) can be. So it may be that you need to keep at least 1 and at most 3 empty lots between any two houses you build. At the end of the street, only the maximum gap comes into play; you can't have a gap larger than the maximum gap between the last house and the end, but you can have a gap smaller than the minimum gap.
Your job is to write a program gaps that computes the maximum possible total reward you can obtain. Your program should take the minimum and maximum gaps as arguments and the list of rewards as a sequence of white-space separated integer values suitable for parsing with scanf, terminated by end-of-file. Your program should print the value of the maximum total reward and a summary string that shows the positions that are included, with a '0' character for any position that is not marked and a '1' for any position that is marked.
For example, suppose that the houses have rewards 1 2 3 4 5 6 7 and that the minimum gap is 1 and the maximum gap is 3. Then the optimal placement is 1 3 5 7 with total reward 16. Your program computing this result might look like this:
$ echo 1 2 3 4 5 6 7 | ./gaps 1 3 16 1010101
Alternatively, perhaps you are penalized for building houses (but must do so anyway). We could model this as a negative reward vector -1 -2 -3 -4 -5 -6 -7. If the minimum gap is 1 and the maximum gap is 3 as before, the optimal solution is to build just the house in the middle, leaving a permitted gap of 3 on either side:
$ echo -1 -2 -3 -4 -5 -6 -7 | ./gaps 1 3 -4 0001000
If we reduce the maximum gap to 2, then the optimum is to take the -2 and the -5, with a gap of 2 between them and a gap of 2 on the right side of -5:
$ echo -1 -2 -3 -4 -5 -6 -7 | ./gaps 1 2 -7 0100100
It's easy to see this because if we move the house at -5 to the right, our costs go up, and -2 is the least painful house to build if we want to prevent a gap of more than 2 empty lots to the left of -5.
Here's a longer input that shows how an optimal solution can run into both the minimum and maximum gap value:
$ echo 1 2 3 4 5 6 -7 -8 -9 -10 -11 -12 -13 -14 15 | ./gaps 1 4 17 010101000100001
For complicated inputs, it may be harder to figure out the optimum value by hand, and for large inputs, it will be expensive to try all possibilities. We recommend attacking the problem using DynamicProgramming.
2. Submitting your assignment
Submit your source files using /c/cs223/bin/submit 9 as usual. If the only file you need is called gaps.c, you do not need to submit anything else; otherwise, you should submit a Makefile as well. You can run /c/cs223/bin/testit 9 public to check your submitted file using the public test script in /c/cs223/Hwk9/test.public, which may or may not resemble the final test script.
3. Sample solution
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <limits.h>
5 #include <string.h>
6
7 static int
8 max(int x, int y)
9 {
10 if(x > y) {
11 return x;
12 } else {
13 return y;
14 }
15 }
16
17 /* Find value of optimal choice placement of marks
18 * such that there are no regions between marks
19 * with less than minGap empty spots
20 * and none with more than maxGap empty spots.
21 *
22 * Returns malloc'd string describing placement '0' = no mark '1' = mark.
23 * Caller should free this.
24 *
25 * Puts value in *value.
26 */
27 char *
28 bestPlacement(int n, const int *reward, int minGap, int maxGap, int *value)
29 {
30 int *best; /* best[i] is best value for any prefix ending with a mark on i */
31 int *prev; /* prev[i] is previous mark (or INT_MIN if no previous mark) for best sequence */
32 char *summary; /* summary string to return */
33 int i;
34 int j;
35 int prevValue;
36 int last; /* last value taken, or INT_MIN if no values taken */
37
38 assert(minGap <= maxGap);
39
40 best = malloc(n * sizeof(*best));
41 assert(best);
42
43 prev = malloc(n * sizeof(*prev));
44 assert(prev);
45
46 for(i = 0; i < n; i++) {
47 prev[i] = INT_MIN;
48 if(i <= maxGap) {
49 /* could have i all by itself */
50 best[i] = reward[i];
51 } else {
52 /* start here and work up */
53 /* prev[i] will be overwritten later */
54 best[i] = INT_MIN;
55 }
56
57 /* consider all possible previous marks */
58 for(j = i-minGap-1; j >= 0 && j >= i - maxGap - 1; j--) {
59 prevValue = best[j] + reward[i];
60 if(prevValue > best[i]) {
61 best[i] = prevValue;
62 prev[i] = j;
63 }
64 }
65 }
66
67 /* last mark must be no earlier than n - maxGap - 1 */
68 /* if maxGap >= n, we might have no marks at all */
69 last = INT_MIN;
70 if(maxGap < n) {
71 *value = INT_MIN;
72 } else {
73 *value = 0;
74 }
75
76 for(i = max(0, n - maxGap - 1); i < n; i++) {
77 if(best[i] > *value) {
78 *value = best[i];
79 last = i;
80 }
81 }
82
83 /* construct output string */
84 summary = malloc(n+1);
85
86 assert(summary);
87
88 memset(summary, '0', n);
89 summary[n] = '\0';
90
91 for(i = last; i != INT_MIN; i = prev[i]) {
92 summary[i] = '1';
93 }
94
95 free(best);
96 free(prev);
97
98 return summary;
99 }
100
101 #define INITIAL_REWARD_SIZE (32)
102
103 int
104 main(int argc, char **argv)
105 {
106 int minGap; /* minimum gap */
107 int maxGap; /* maximum gap */
108 int *reward; /* array of rewards */
109 int n; /* number of values in reward */
110 int size; /* size of reward */
111 int nextVal; /* for reading in next value */
112 char *summary; /* summary string */
113 int value; /* value */
114
115 if(argc != 3) {
116 fprintf(stderr, "Usage: %s minGap maxGap\n", argv[0]);
117 return 1;
118 }
119
120 minGap = atoi(argv[1]);
121 maxGap = atoi(argv[2]);
122
123 size = INITIAL_REWARD_SIZE;
124 reward = malloc(size * sizeof(*reward));
125
126 n = 0;
127
128 while(scanf("%d", &nextVal) == 1) {
129 if(n >= size) {
130 size *= 2;
131 reward = realloc(reward, size * sizeof(*reward));
132 }
133
134 reward[n++] = nextVal;
135 }
136
137 summary = bestPlacement(n, reward, minGap, maxGap, &value);
138
139 printf("%d\n", value);
140 puts(summary);
141
142 free(reward);
143 free(summary);
144
145 return 0;
146 }