Question

IOs, mltipncation, division) counts as one step of the algorithm. sheet, the ith problem is worth pi points. The problems must be solved in the given order, but it is possible to skip (not to solve) some of them. Furthermore, if a student solves the ith problem, then she/he gets so exhausted that she/he must skip the next fi problems (of course she/he may skip O(n) running time dynamic programming algorithm that determines the maximum possible points that are numbers p,f for i = 1,2, ...n. problems in an exam 7. There are n more. It is also possible to skip the first few problems.) Give an a student can obtain. The input of the algorithm

Answer 1

For solving this dynamic programming question, we will have the vectors (or lists) P and F. Let us assume that the size of each is N.

At every index (i) the dynamic programming decision is Ans(P, F, i) = max(P(i) + Ans(P, F, i + 1+ F(i)), Ans(P, F, i+1))

Understanding the recursion:

We are deciding to find the max of two terms - Term 1: P(i) + Ans(P, F, i + 1 + F(i)) and Term 2: Ans(P, F, i+1)

Term 1 denotes the decision when we take up the given question and skip the next F(i) problems.

Term 2 denotes the decision when we don't take up the question (i) and think what if this question never exists at all.

Ans(P, F, i) is dependent on Ans(P, F, i + 1+ F(i)) and Ans(P, F, i+1)

This means that we have to solve from the last element since prior element solution depends on elements that appear latter.

Assume P = [1, 5, 1] F=[1,0,1]

We compute vec V of size 3 as follows

V[2] = Take P[2] since we don't have anything else so V[2] = 1

V[1] = Take either P[1] = 5 and add V[1 +1+ F[1]] = V[1+1+0] = V[2] = 1 so V[1] = 6. The other option was to not take P[1] and just take V[2] = 1. 6 > 1 we put V[1] = 6

V[0] = Take either P[0] and skip the next question F[0] = 1. so either V[0] = P[0] + V[2] or V[0] = V[1]. The simple answer is V[0] = V[1] = 6

Hence this is O(N) algorithm