Dynamic Programming Help

Question

Sometimes I can see the recurrence relationship and other times I cannot. This is one of those times. I've gone through a few iterations of trying to solve it but I also find a set of values where my idea fails. If I go exponenetial I can figure it out... but that's a specific no-no.

I'm good with nudges in the right direction. Please make it a little strong though.

Problem

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up your time, you’ve come up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, 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. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

Answer 1

When you encounter these types of problems, the typical thing to do is to find some "decision scheme" that can decompose your big problem into a series of smaller problems. The gist of this problem is finding a set $(h_1, \dots, h_n)$ that maximizes your mean grade $\frac{\sum_{i \le n} f_i(h_i)}{n}$ subjected to the constraint that $\sum\limits_{i \le n} h_i \le H$. Notice that maximizing $\frac{\sum_{i \le n} f_i(h_i)}{n}$ is equivalent to just maximizing $\sum\limits_{i \le n} f_i(h_i)$ since the denominator $n$ is independent of the choices of $(h_1, \dots, h_n)$ that we make.

Now, there are various dynamic programming schemes that we can choose to solve this problem, each of which depends on some special interpretation of an "optimal functional" that we define. For me, the intuitive one is based on the idea of variable elimination, in which we eliminate one of the variables $h_i$ at each turn.

Here, let $\textrm{Best}(k, h)$ denote the maximum cumulative grade you can gain for the classes $C_k, C_{k+1}, \dots, C_n$ so that you spend no more than $h$ hours on all of their final projects. Given this interpretation, it is clear that our problem is to find $\textrm{Best}(n, H)$.

Now comes the fun/interesting part. First, we need to convince ourselves that this functional displays what we would call an "optimal substructure." In layman's words, this claims that if we know the best distribution of no more than 5 hours to Networking and Programming Languages' final projects, then we also know the best distribution of 8 hours to the Networking, PL, and OS' final projects if we decide to allocate 3 hours to the OS project. It's simple, we just use the same optimal budget of 5 hours for Networking and Programming languages that we already have.

In other words, this optimal substructure property guides us on the decision we have to make at each turn (because we don't have to worry about the subproblems). Here, $\textrm{Best}(k, h)$, according to the substructural property we've introduced above, must make a decision on what $h_k$ should be assigned. In addition, it must

1. Ensure that $h_k$ does not exceed its allocated hours of $h$, and
2. Maximize the grades contingent on the choices that it can make.

Therefore, when we consider the problem of computing $\textrm{Best}(k, h)$, there's a range of valid decisions that we can make, each corresponds with an assignment of a single value to $h_k$. For example, say I'm considering $\textrm{Best}(\textbf{Networking}, 5)$, which corresponds to the maximum cumulative grade that I can get in classes Networking, PL, and OS with only 5 hours to distribute between them. Now, I have to make a decision about how I will budge for Networking. Say I budget exactly 0 hours to networking, then I can spend 5 hours on PL and OS; alternative, I can budget 1 hour to networking and spend 4 hours between PL and OS, 2 hours to networking and 3 between PL and OS, etc. Each choice of time budget for Networking also determines a subproblem that I have to solve between PL and OS with the remaining time. Once we consider all of these choices (and subproblems), we must then commit to the problem that will give us the best solution.

This thought process should yield a recurrence for Best that can be computed in some increasing order of its parameter. This computation then takes the form of a tabulation over an $n \times H$ grid, each time spending approximately $O(k)$ (where $k \le n$ is the column number) time between the $O(k)$ choices, which gives an $O(n^2 H)$ algorithm.