Youre taking n courses and every single one of them has a final project that you still have to get around to finishing up. Each project will be graded on the following scale: it will be assigned an integer number on a scale of 1 to g > 1; with higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. Because its the end of the semester and youve gotten into some bad habits, you realize that you procrastinated too much and now you only have a total of H > n hours in which to work on the n projects cummulatively and you need to figure out the best way to divide up this time to maximize your average grade overall. For simplicity, assume that H is a positive integer and youll spend an integer number of hours on each projects.

To figure out how best to divide up the time, youve come up with a set of functions [fi : i = 1, 2, , n] for each of your courses: if you spend h H hours on the project for course i, then youll get a grade of fi(h). You may make the assumption that the functions are non-decreasing (i.e if h < h0 , then fi(h) fi(h 0 )). Given these functions, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi , is as large as possible. The algorithm should be polynomial in n and H.

Show the substructure with explanation and pseudo code (with explanation) that calculates the best total grade.