(U&G-required)[100points]Assume that you are given a task of managing the placement of commercial advertisements along a freeway that runs from west to east for a distance of D miles. The freeway has a set of n possible sites for the advertisement locations, given by positions x1,x2, ...,xnalong the freeway, all within the interval [0, D], measured in miles from the western end. Placing an advertisement at a location x i will earn you a revenue ri> 0.The rules for placing the advertisement boards require that no two commercials can be placed within less than or equal to 5 miles of each other. Your job is to place the advertisements at a subset of the possible sites in such a way that you maximize yourtotal revenue. Develop a dynamic programming algorithm that finds the optimal value and the optimal solution for this problem using the steps outlined below. (a) [20 points] Write a recursive formula that illustrates how the optimal valuefor the revenue can be computed from optimal values to subproblems. Note:this part should not contain any code, just the recursive formula. Submit: the recursive formula, along with definitions and explanations on what is computed(in pdf format).(b) [30 points] Write an algorithm that computes the optimal value to this problem, based on the recurrence above.The algorithm should save in an output file the optimal values for all the subproblems as well as the optimal value for the entire problem. Implement your algorithm in C/C++ and run it on the following values:D= 20, n= 4{x1, x2, x3, x4} = {6, 7, 12, 14}{r1, r2, r3, r4} = {5, 6, 5, 1}
Submit: -The source file containing youralgorithm (name the file advertise_pb.cor advertise_pb.cpp)-The output file created by your algorithm (name the file advertise_pb_out.txt), which contains:−The table with the optimal values to all subproblems(save the entire table)−The optimal value for the entire problem (indicate this on a separate line after the table, even if the value is found in the table above)(c) [20 points] Update the algorithm you developed in part (b) to enable the reconstruction of the optimal solution, i.e.,to store the choices you made when computing the optimal values for each subproblem in part (b).Your updated C/C++ program should store those choices in an auxiliary table and then save that table in an output file. Include these updates in your implementation from point (b). Submit: -The source file containing your algorithm (name the file advertise_pc.cor advertise_pc.cpp)-The output file created by your algorithm (name the file advertise_pc_out.txt), which contains the values of the table containing the additional information(choices)needed to reconstruct the optimal solution(print the entire table).(d) [30 points] Using the additional information computed and saved to file in part (c), write an algorithm that prints the optimal solution, i.e., it prints the locations you choose to place the commercial advertisements.Your algorithm should save this optimal solution in an output file.Implement this algorithm in C/C+.Submit:-The source file containing your algorithm (name the file advertise_pd.cor advertise_pd.cpp)
-The output file created by your algorithm (name the file advertise_pd_out.txt) that contains the optimal solution to the problem given by the numerical values in part(b).