Question

Shindler gives lots of homework assignments, each of which have an easy version and a hard version1. Each student is allowed, for each homework, to submit either their answer to the easy version (and get ei > 0 points) or the hard version (and get hi > 0 points, which is also guaranteed to always be more than ei) or to submit neither (and get 0 points for the assignment). Note that ei might have different values for each i, as might hi. The values for all n assignments are known at the start of the semester.

The catch is that the hard version is, perhaps not surprisingly, more difficult than the easy version. In order for you to do the hard version, you must have not done the previous assign- ment at all: neither the easy nor the hard version (and thus are more relaxed, de-stressed, etc). Your goal is to maximize the number of points you get from homework assignments over the course of the semester. Give an efficient dynamic programming algorithm to determine the largest number of points possible for a given semester’s homework choices.

Answer 1

To maximize the student's scores, we can model the recurrence as:

The pseudocode for the algorithm can be given as:

The initialization condition for dparray is mentioned in the comments of the code. (In both the textual as well as the screenshot format)

Code in python:

easy_list = [5,10,10,15,20]

hard_list = [10,12,15,25,30]

dparr = [0]*len(easy_list) #intitialize the dparray with the size of easylist and all will have 0 value

dparr[0] = hard_list[0]     #This is given as the first condition because, the user will always be relaxed and de-stressed at the beginning of the term, hence will select the hard question.

dparr[1] = max(dparr[0] + easy_list[1], hard_list[1])  #This is the second condition because for the second day he can either do the hard question that day andskip the earlier question

                                                       #Otherwise he can also do the question of the previous day and complete the easy one for this day.

for i in range(2,len(easy_list)):

    dparr[i] = max(dparr[i-1] + easy_list[i], dparr[i-2] + hard_list[i])    

print(dparr[len(dparr) - 1])

Code Screenshot:

Output Screenshot:

Please refer to the screenshot of the code to understand the indentation of the code".