Yuckdonald's Restaurant Placement
Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH). The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order, m[1], m[2], …, m[n]. The constraints are:
• At each location, Yuckdonald's may open at most one restaurant. The expected profit from opening a restaurant at location i is p[i], where p[i] > 0.
• Any two restaurants should be at least k miles apart, where k is a positive integer.
For each i, let prev(i) = the largest index j < i with m[i] − m[j] ≥ k (0 if none). This is the "take/skip" shape — a 1-D Knapsack cousin.
If we open i, the previous restaurant can be no later than prev(i), so we add the best profit up to there. If we skip i, we inherit T(i-1).
Note: computing every prev(i) up front with a scan is O(n²); a two-pointer pass makes it O(n), giving O(n) fill. State whichever your recurrence implies — the exam wants consistency, and O(n²) is safe and correct.
Optional pseudocode not required by Ed #9
A mechanical translation of the recurrence. The exam grades the recurrence, not this.
function Yuckdonalds(m[1..n], p[1..n], k): # precompute prev(i) = largest j < i with m[i]-m[j] >= k, else 0 for i = 1 to n: prev[i] = 0 for j = i-1 down to 1: if m[i] - m[j] >= k: prev[i] = j; break T[0] = 0 for i = 1 to n: T[i] = max(T[i-1], p[i] + T[prev[i]]) return T[n]
Try it yourself
worked example + self-testRecurrence: T(0)=0; T(i)=max{T(i−1), p[i]+T(prev(i))}. Answer T(n).
positions m = [1, 3, 6, 10, 14, 18], profits p = [5, 6, 5, 11, 4, 9], k = 5
2, 4, 6 (positions 3, 10, 18; profits 6+11+9). Spacing 7 and 8, both ≥ 5. ✓ Why the DP is needed: a naive left-to-right greedy (open, then skip until 5 miles clear) opens miles 1, 6, 14 for only 14 — it grabs the cheap early location 1 and gets blocked out of the profit-11 location at mile 10. The DP's skip-vs-open weighing finds 26.positions m = [2, 5, 9, 12, 16], profits p = [4, 7, 3, 8, 6], k = 4