You are given a sequence of n items such that each item i has value vi and if yo

Question

You are given a sequence of n items such that each item i has value vi and if you buy item j you can not buy items j + 1 or j + 2. Your goal is to maximize the sum of the values of all the items purchased.

Give an O(n) runtime algorithm to find a set of items fitting these criteria, prove the correctness of your algorithm, and analyze its runtime.

Part 2 grading:

[10 points] Algorithm: Your algorithm generally has a correct idea and has a runtime of O(n)

[20 points] Correctness Proof: Your algorithm is correct on all inputs, has a runtime of O(n), and your proof of correctness is logically sound and complete

[5 points] Runtime Analysis: Your algorithm has a runtime of O(n) and you correctly analyzed the runtime of your algorithm

[20 points] Implementation: You correctly implemented your algorithm in code and the implementation is correct on all inputs with runtime O(n)

Explanation / Answer

Hello Student!

I am happy to help you!

(a) Consider our array to be -

item - 1, 2, .... n ; value - x, y, ... n

Now, we have the constraint that we cannot pick the j+1 and j+2 element. Now, if we start from the 0th index we would find difficulty to find the starting point. But, if we start from the end we will be determined that how to start.

Here's the explanation.

1 ..... n-4 n-3 n-2 n-1 n

For, last element best possible case would be. If we pick it.

1 ..... n-4 n-3 n-2 n-1 n

For, n-1th element best case would be (because we cannot pick any element)

1 ..... n-4 n-3 n-2 n-1 n

1 ..... n-4 n-3 n-2 n-1 n

Now, for n-3 the max value will be max(arr[n-3], arr[n-3]+arr[n])

And, for n-4 the max value will be max(arr[n-4], arr[n-4]+arr[n-1], arr[n-4], arr[n])

So, the formulae comes out to be-

arr[k] = arr[k] + max(1,.. arr[k+3], arr[k+4].. arr[last_picked-1])

The algorithm will have a runtime complexity of O(n) if we are able to compute the max(1,.. arr[k+3], arr[k+4].. arr[last_picked]) in O(n). How we would be able to compute it?

We will make a maximum array.. which will have the maximum value from the kth to the last picked value

A[n] = val[n]

A[n-1] = val[n-1]

A[n-2] = val[n-2]

maxArr[n] = val[n]

maxArr[n-1] = max(val[n], val[n-1])

maxArr[n-2] = max(val[n], val[n-1], val[n-2])

for i = n-3 ; i >= 0 ; i--

A[i] = max(val[i]+maxArr[i+3],maxArr[i+3]);

maxArr[i] = max(A[i], maxArr[i-1]);

end

ans = INT_MIN;

for i = 0 ; i <= n ; i++

ans = max(ans, A[i]);

end

return ans;

Test case :

Given arr : 15, 12, 24, 27, 23, 25

MaxArr will be : 49, 49, 49, 27, 25, 25

Maximum sum will be after j+1, j+2 will be - 49

Thank you. Feel free to ask anything. Please upvote, if you like the answer. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.