5) There is an s miles long road, with n possible locations for advertisements at distances...
5) There is an s miles long road, with n possible locations for advertisements at distances di,... , dn from the beginning of the road. Putting an advertise- ment at the i'th location brings in revenue pi. Two advertisements cannot be located closer than distance from each other. Find a set of locations for the advertisement bringing in maximal revenue. a) Design a dynamic programming algorithm for this problem b) Use your algorithm to find the optimal solution for distances 5, 9, 17, 23, revenues 4, 8, 6, 1 and distance 10 Hint: Let rj be the maximal revenue achievable by locations on the first j miles stretch of the road. For every j, let prev(j) be the location preceding d, which is at least distance from the j'th location. Determine an optimal ity relation for rj involving these quantities and use it to design a dynamic programming algorithm.