6.3 yuckulonald's is considering opening a series of restaurants along quaint valley highway (qvh). the it possible locations are along a straight line, and the distances of these locations from the start of ovh are in miles and in increasing ander, m. the constraints are as follows at each location. yuckdonald's may open at most one restaurant. the expected profit from opening a restaurant at location i is p. where po and/ 1.2. any two restaurants should be at least k miles apart, where k is a positive integer give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.a) Carefully read and understand the problem statement. Consider the following problem instance: Locations: mı = 10 miles, m2= 20 miles, m3 = 25 miles, m4= 30 miles, and ms= 40 miles, with k = 10 miles, and Profits: p.= 100, p2 = 100, P3 = 110, P4 = 100, and ps = 100. Show that the greedy technique, which consists in choosing the locations in decreasing order of profit, does not yield the optimal solution. b) To find an efficient algorithm to compute the maximum expected total profit, subject to the given constraint (any two restaurants should be at least k miles apart), we first define a recurrence relation, as is usually the case with Dynamic Programming. Let P(1) be the maximum profit obtained by considering the first j locations. Note that in this problem, we cannot merely write P(j) in terms of P(-1) since location j might not satisfy the constraint condition: "Any two restaurants should be at least k miles apart". For example, in the problem instance of part a), we cannot choose the second and third locations, since m2 = 20 and m3= 25; in other words, locations 2 and 3 are not at least 10 units apart. So, let us define prev(j) to be the largest index i, to the left of location j, and at least k miles from j; in other words, m=m; - k. Note that prev(j) should be 0 if no such index (i.e., index i) can be found. 1) Express P(i) in terms of P(-1), with the help of prev(j). 2) Give an efficient algorithm to compute the maximum expected total profit subject to the given constraints.