Let and be positive integers. For , let be a univariate real-valued function defined in the integer domain and let be for negative integer . Any non-negative integer solution that satisfies is called a feasible solution. In addition, a feasible solution that maximizes the objective function is called an optimal solution and the objective function value at the solution is called the optimal value. This problem is expressed as follows.
Unless the non-increasing assumption of (1) holds, the greedy algorithm does not always output an optimal solution of . To apply dynamic programming, we consider the following problem in which and in are replaced with and , respectively.
The optimal value of the problem is denoted by . Answer the following questions.
(2-1) Express only with and for any non-negative integer in the case of .
(2-2) Write a pseudo-code of a dynamic programming algorithm within 15 lines to output the optimal value of . Hereafter, this algorithm is called .
(2-3) Show that the optimal value of is obtained by the dynamic programming algorithm .
(2-4) Answer the computational complexity of the dynamic programming algorithm and the computational complexity of the greedy algorithm . Ignore the computational cost of calculating .